Advantages of Trie Data Structure
Tries is a tree that stores strings. Maximum number of children of a node is equal to size of alphabet. Trie supports search, insert and delete operations in O(L) time where L is length of key.
Hashing:-In Hashimg, we convert key to a small value and the value is used to index data. Hashing supports search, insert and delete operations in O(L) time on average.
Self Balancing BST :The time complexity of search, insert and delete operations in a self-balancingBinary Search Tree (BST)(likeRed-Black Tree,AVL Tree,Splay Tree, etc) is O(L Log n) where n is total number words and L is length of word. The advantage of Self balancing BSTs is that they maintain order which makes operations like minimum, maximum, closest (floor or ceiling) and k-th largest faster. Please referAdvantages of BST over Hash Tablefor details.
Why Trie? :-
- With Trie, we can insert and find strings in _O(L) _time where _L _represent the length of a single word. This is obviously faster that BST. This is also faster than Hashing because of the ways it is implemented. We do not need to compute any hash function. No collision handling is required (like we do in open addressing and separate chaining )
- Another advantage of Trie is, we can easily print all words in alphabetical order which is not easily possible with hashing.
- We can efficiently do prefix search (or auto-complete) with Trie
Issues with Trie :-
The main disadvantage of tries is that they need lot of memory for storing the strings. For each node we have too many node pointers(equal to number of characters of the alphabet), If space is concern, thenTernary Search Treecan be preferred for dictionary implementations. In Ternary Search Tree, time complexity of search operation is O(h) where h is height of the tree. Ternary Search Trees also supports other operations supported by Trie like prefix search, alphabetical order printing and nearest neighbor search.
The final conclusion is regarding _tries data structure _is that they are faster but require _huge memory _for storing the strings.