TRIE data structure Part 4 : The SEARCH Algorithm

• 1
• 2
• 3
• 4
• 5
• 6
• 7

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

1. For each character in the string, see if there is a child node with that character as the content.
2. If that character does not exist, return false
3. If that character exist, repeat step 1.
4. Do the above steps until the end of string is reached. 
5. When end of string is reached and if the marker of the current Node is set to true, return true, else return false.

Using the above algorithm, lets perform a search for the key "do".

1. 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".
2. 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".
3. 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"

1. 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".
2. 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".
3. 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".
4. 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".
5. 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; 
 }

The above java code does the search operation in the TRIE data structure. We shall look more into the running time and efficiency of TRIE in the next part.

Cheers,
Bragaadeesh.