Trie Data Structure
In this blog, we talk about Trie, which is an efficient information retrieval Data Structure.
If we want to search for a word say admire, in Dictionary we first go to a then we move to d and then we move to m and so on. There might be other words that start with a for eg, audit, In this case, we start from a, then go to u, and so on. Trie data structure also works in a similar way. It is a tree kind of representation, where each node has a maximum of 26 children (ALPHABET_SIZE). Trie is also known as a prefix tree. Trie is a sorted tree-based data structure that stores the set of strings. Each node in the Trie will have pointers equal to the number of characters of the alphabet. Search complexities can be optimal( keyword length) using Trie. If we use Tree instead of Trie, to retrieve the information, then a well-balanced BST will take O(M * logN) time complexity, where M is the maximum length of the key and N is the number of nodes in the Trie. Whereas, Trie takes O(M) time complexity. However, the memory requirement for Trie is O(S * M * N), where S is ALPHABET_SIZE(26), M is the length of the keyword and N is the number of nodes in the Trie.
In Trie, root always represents null. Each node can have a maximum of 26 children(A to Z). Each branch represents the possible branches of the keyword. We need to mark the last node of every key as the end of the word node. A Trie node field isEndOfWord is used to distinguish the node as the end of word node. Insert, Search and Delete operations are possible with Trie. If we want to insert an element, we will first create a root and then we make the children null. There can be a maximum of 26 child nodes (ALPHABET_SIZE). Every character of the input key is inserted as an individual Trie node. Note that the children are an array of pointers (or references) to next-level trie nodes. If the input key is new or an extension of the existing key, 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.
Key Takeaways
- Trie is faster than hash tables and binary trees
- Space complexity is more when compared to Hash tables.
Applications of Trie
- Spell Checker
- Auto-complete
- Browser History.
Conclusion
In this article, we have seen about Trie data structure and how it optimizes the search results. We have also seen the time and space complexities of Trie and also the applications of Trie.
