Advantages of Trie:
- With Trie, we can insert and find strings in
O(L)
time where L represent the length of a single word. A BST performsO(log n)
comparisons of keys, wheren
is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takesO(m log n)
time. - Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless.
- Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique.
- By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers. With Trie there is no need to compute any hash function and no collision handling is required.
- Tries require less space in comparison to BST. Because the keys are not stored explicitly, only an amortised constant amount of space is needed to store each key.
- Deletion is straightforward
Disadvantages of Trie:
- The main disadvantage of tries is that they need a lot of memory for storing strings. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That’s a million nodes of overhead.
- A well constructed hash table (i.e. a good hash function and a reasonable load factor) has
O(1)
lookup time. Lookup time in a trie isO(m)
: it depends on the length of the string you’re looking up.