In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed.
Consider the following TRIE as usual.
The search alogirthm involves the following steps
Using the same algorithm, lets perform a search for the key "ball"
Lets understand complexity in next post.
References
http://www.technicalypto.com/2010/04/trie-data-structure-part-4-search.html
Consider the following TRIE as usual.
The search alogirthm involves the following steps
- For each character in the string, see if there is a child node with that character as the content.
- If that character does not exist, return false
- If that character exist, repeat step 1.
- Do the above steps until the end of string is reached.
- When end of string is reached and if the marker of the current Node is set to true, return true, else return false.
- See whether "d" is present in the current node's children. Yes its present, so set the current node to child node which is having character "d".
- See whether "o" is present in the current node's children. Yes its present, so set the current node to child node which is having character "o".
- Since "o" is the end of the word, see whether marker is set to true or false. Marker is set to false which means that "do" is not registered as a word in the TRIE. So, return false.
Using the same algorithm, lets perform a search for the key "ball"
- See whether "b" is present in the current node's children. Yes its present, so set the current node to child node which is having character "b".
- See whether "a" is present in the current node's children. Yes its present, so set the current node to child node which is having character "a".
- See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
- See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
- Since "l" is the end of the word, see whether marker is set to true or false. Marker is set to true which means that "ball" is registered as a word in the TRIE. So, return true
public boolean search(String s){ Node current = root; while(current != null){ for(int i=0;i<s.length();i++){ if(current.subNode(s.charAt(i)) == null) return false; else current = current.subNode(s.charAt(i)); } /* * This means that a string exists, but make sure its * a word by checking its 'marker' flag */ if (current.marker == true) return true; else return false; } return false; }
Lets understand complexity in next post.
References
http://www.technicalypto.com/2010/04/trie-data-structure-part-4-search.html
0 comments:
Post a Comment