Trie | (Insert and Search)
In this blog, we see how to insert and search for a word in a Trie Data Structure.
Processing a string has a variety of real-world applications like Search Engine, Browser History, Spell Checker, auto-complete, etc. Trie is a special kind of data structure that stores strings that can be seen as a tree.
The root of a Trie always represents null. Every node in a trie can contain a maximum of 26 nodes(ALPHABET_SIZE).
static class TrieNode {
TrieNode[] children = new TrieNode[ALPHABET_SIZE];
//isEndWord represents the end of the word.
boolean isEndWord = false;
}
Initially, We initialize the nodes of the root to null. Then we take a key(the word that we want to insert inside in the trie). Every character in the key is inserted as an individual Trie node. Note that the children is an array of pointers (or references) to next-level trie nodes. If the input key is new then, we need to construct non-existing nodes of the key and mark the end of the word for the last node. If the input key is a prefix of the existing key in Trie, we simply mark the last node of the key as the end of a word. The key length determines Trie depth.
Searching for a key is similar to insert operation, however, we only compare the characters and move down. The search can terminate due to the end of a string or lack of key in the trie. In the former case, if the isEndWord field of the last node is true, then the key exists in the trie. In the second case, the search terminates without examining all the characters of the key, since the key is not present in the trie.
Insert and search takes O(key_length) time complexity, whereas the space requirement of Trie is O(S*N*Key_length). Sis the ALPHABET_SIZE(26), N is the number of nodes in the trie.
Read Trie Data Structure to know more about it
Now, let's see the implementation of insertion and search operations in a trie.
public class Trie { // Alphabet size static final int ALPHABET_SIZE = 26; static class TrieNode { TrieNode[] children = new TrieNode[ALPHABET_SIZE]; // isEndWord is true if the node represents end of word boolean isEndWord; TrieNode(){ isEndWord = false;
// Initialise children to null for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = null; }
}; static TrieNode root // If not present, inserts key into trie // else, if the key is prefix of trie node, // just marks leaf node static void insert(String key) {
int level; int length = key.length(); int index; TrieNode curr= root; for (level = 0; level < length; level++) { index = key.charAt(level) - 'a'; if (curr.children[index] == null) curr.children[index] = new TrieNode(); curr = curr.children[index]; } // mark last node as leaf curr.isEndWord = true; }
// Returns true if key presents in trie, else false static boolean search(String key) { int level; int length = key.length(); int index; TrieNode curr= root; for (level = 0; level < length; level++) {
index = key.charAt(level) - 'a'; if (curr.children[index] == null) return false;
curr= curr.children[index];
}
return (curr.isEndWord);
} // Driver code public static void main(String args[]) { // Input keys (use only 'a' through 'z' and lower case) String keys[] = {"ants", "and", "there", "their", "bat", "ball"}; String output[] = {"doesnot in trie", "exists in trie"}; root = new TrieNode();
// Construct trie int i; for (i = 0; i < keys.length ; i++) insert(keys[i]); // Search for different keys if(search("bat") == true) System.out.println("bat ---> " + output[1]);
else System.out.println("bat---> " + output[0]); if(search("their") == true) System.out.println("their ---> " + output[1]); else
System.out.println("their---> " + output[0]); }}
Conclusion:
In this article, we have seen how to insert and search for a word in Trie. Trie is a special data structure, which makes search results optimized. However, what it lags in terms of space, more than makes up for it in terms of time.
