tag:blogger.com,1999:blog-6294663875929591018.post5156955383882717618..comments2023-09-24T03:12:58.137-07:00Comments on Ramblings of a techie: TRIE data structure Part 2 : Node and TRIE class in JavaBragBoyhttp://www.blogger.com/profile/01173019524783723568noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6294663875929591018.post-22853054043113253222014-11-07T22:54:01.534-08:002014-11-07T22:54:01.534-08:00Thanks a lot for the tutorial, Bragaadeesh. It'...Thanks a lot for the tutorial, Bragaadeesh. It's helped me a lot. However, I think there is something wrong with the search() method. I understand the need to ensure the current node isn't null, but I don't think the for-loop should be within a while loop. Please take a look at it again and let me know if there's something I'm missing.stralohttps://www.blogger.com/profile/15504828531101714792noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-14948122761094418462014-01-22T01:01:56.763-08:002014-01-22T01:01:56.763-08:00Space complexity of Anindya's code is too much...Space complexity of Anindya's code is too much,there are many empty cells in this implementation using hashmaps. Hence, not a desired code by manyAnonymoushttps://www.blogger.com/profile/14344511750657653427noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-78215616229262268992012-07-28T08:24:47.204-07:002012-07-28T08:24:47.204-07:00I completely agree with sushma .... deletion code ...I completely agree with sushma .... deletion code requires some correctionVaibhav Sawanthttps://www.blogger.com/profile/00846498843531051847noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-77007045428910163352011-07-16T02:18:03.278-07:002011-07-16T02:18:03.278-07:00Thanks for the code. A few questions about Anindya...Thanks for the code. A few questions about Anindya's delete code :-<br />1)if(child.prefixes == 1){<br />current.children.remove(Character.valueOf(c));<br /><br />lets say the words cart, can, camera are inserted. Now camera is deleted. The above code removes "m" from the children list of "a". How to delete the memory allocated for "e,r,a" nodes.<br /><br />2) In delete function<br />// since the word is removed now, set the flag to false<br />current.isWord = false;<br /><br />Lets say do, door, does are inserted. Now "does" is deleted. So this sets "o" node a not a word. But "do" is a word.Sushmahttps://www.blogger.com/profile/02243057320659281787noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-46234628777538904272011-06-22T11:54:22.803-07:002011-06-22T11:54:22.803-07:00This comment has been removed by the author.Varunhttps://www.blogger.com/profile/03973948748229723614noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-71068863539225469412011-05-09T07:16:19.484-07:002011-05-09T07:16:19.484-07:00That's neat stuff. How would a the basic imple...That's neat stuff. How would a the basic implementation of a delete method look for this program?johnhttps://www.blogger.com/profile/09611513371871148404noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-72697786265807889322011-05-01T10:01:13.952-07:002011-05-01T10:01:13.952-07:00@Anindya : great job!@Anindya : great job!BragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-82305066240700562812011-04-29T23:10:56.465-07:002011-04-29T23:10:56.465-07:00Above is a complete implementation inspired from B...Above is a complete implementation inspired from Bragaadeesh introductory tutorial. It helped me a lot in undertsanding the concepts hence I thought of posting the entire code myself. If anyone is interested practising problem, have a look at the following Topcoder problems<br /><br />http://www.topcoder.com/stat?c=problem_statement&pm=7411<br /><br />http://www.topcoder.com/stat?c=problem_statement&pm=6215Anindyahttps://www.blogger.com/profile/14181137495814847426noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-30837273337106413312011-04-29T23:07:55.623-07:002011-04-29T23:07:55.623-07:00import java.util.HashMap;
import java.util.Map;
p...import java.util.HashMap;<br />import java.util.Map;<br /><br />public class Trie {<br /> private static class Node {<br /> private boolean isWord = false; // indicates a complete word<br /> private int prefixes = 0; // indicates how many words have the prefix<br /> private Map children = new HashMap(); // references to all possible children <br /> }<br /><br /> private Node root = new Node();<br /> <br /> /**<br /> * Inserts a new word into the trie<br /> * @param word<br /> */<br /> public void insertWord(String word){<br /> if(searchWord(word) == true) return;<br /> <br /> Node current = root;<br /> for(char c : word.toCharArray()){<br /> if(current.children.containsKey(Character.valueOf(c))){<br /> Node child = current.children.get(Character.valueOf(c));<br /> child.prefixes++;<br /> <br /> current = child;<br /> }else{<br /> Node child = new Node();<br /> child.prefixes = 1;<br /><br /> current.children.put(Character.valueOf(c), child);<br /> current = child;<br /> }<br /> }<br /> // we have reached the endof the word, hence mark it true<br /> // if during a search we reach the end of the search string and this <br /> // flag is still false, then the search string is not registered as a valid <br /> // word in the trie but is a prefix<br /> current.isWord = true;<br /> }<br /><br /> /**<br /> * Searches for a word in the trie<br /> * @param word<br /> */<br /> public boolean searchWord(String word){<br /> Node current = root;<br /> for(char c : word.toCharArray()){<br /> if(current.children.containsKey(Character.valueOf(c))){<br /> current = current.children.get(Character.valueOf(c));<br /> }else{<br /> return false;<br /> }<br /> }<br /> // if at the end of the search of entire word the boolean variable is <br /> // still false means that the given word is not regitered as a valid <br /> // word in the trie, but is a prefix<br /> return current.isWord;<br /> }<br /> <br /> /**<br /> * Deletes a word from the trie<br /> * @param word<br /> */<br /> public void deleteWord(String word){<br /> if(searchWord(word) == false) return;<br /> <br /> Node current = root;<br /> for(char c : word.toCharArray()){ <br /> Node child = current.children.get(Character.valueOf(c));<br /> if(child.prefixes == 1){<br /> current.children.remove(Character.valueOf(c));<br /> return;<br /> }else{<br /> child.prefixes--;<br /> current = child;<br /> }<br /> }<br /> // since the word is removed now, set the flag to false<br /> current.isWord = false;<br /> }<br /> <br /> public static void main(String[] args) {<br /> Trie trie = new Trie();<br /> trie.insertWord("ball");<br /> trie.insertWord("balls");<br /> trie.insertWord("bat");<br /> trie.insertWord("doll");<br /> trie.insertWord("dork");<br /> trie.insertWord("dorm");<br /> trie.insertWord("send");<br /> trie.insertWord("sense");<br /> <br /> // testing deletion<br /> //System.out.println(trie.searchWord("ball"));<br /> //trie.deleteWord("ball");<br /> //System.out.println(trie.searchWord("ball"));<br /> //System.out.println(trie.searchWord("balls"));<br /> <br /> // testing insertion<br /> //System.out.println(trie.searchWord("dumb"));<br /> //trie.insertWord("dumb");<br /> //System.out.println(trie.searchWord("dumb"));<br /> //trie.deleteWord("dumb");<br /> //System.out.println(trie.searchWord("dumb"));<br /> }<br />}Anindyahttps://www.blogger.com/profile/14181137495814847426noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-568914340877244992010-11-13T23:48:39.486-08:002010-11-13T23:48:39.486-08:00@cutelyaware: Yes, i have not implemented the dele...@cutelyaware: Yes, i have not implemented the delete() method, the simple reason is to keep things simple. I don't want to put in a lot of methods in one stretch in this introductory tutorial.BragBoyhttps://www.blogger.com/profile/01173019524783723568noreply@blogger.comtag:blogger.com,1999:blog-6294663875929591018.post-48581866168102651682010-11-13T14:46:46.549-08:002010-11-13T14:46:46.549-08:00Your implementation does not allow for deletion of...Your implementation does not allow for deletion of words. IOW, your trees can only grow and will never shrink which could be a problem for some applications.cutelyawarehttps://www.blogger.com/profile/16190785261752468280noreply@blogger.com