3 ms·
One might note that properly implemented hash tables also have O(k) lookup times. And in fact, much of the time well-tuned hash tables outperform well-tuned tr
by aidenn0 10y ago
One might note that properly implemented hash tables also have O(k) lookup times. And in fact, much of the time well-tuned hash tables outperform well-tuned tries.
Tries still have some advantages though:
1) The naive implementation of a trie of using an alphabet-sized vector for the child nodes is much closer to the ideal performance than the naive implementation of a hash table. If I had to implement a dictionary on short notice, I would use a trie.
2) Tries preserve ordering, while still allowing O(1) [in the number of items in the dictionary] insert, removal and lookup. If you need to get the key that is lexicographically next or previous, to another key, or you need to find the two keys that bound a particular value, it's a great structure to use. Comparison based trees can also do this but not with constant time insert and remove.
For a really space-efficient trie-like structure, see crit-bit trees[1] which are basically a space-efficient radix tree with on a binary alphabet (so each internal node has a fanout of exactly 2).
1: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html