SamuraiCrow wrote:
The binary and ternary search trees would be slower than the hash or the trie. The ternary search tree would be O(log n) time complexity while the trie and hash have typical time complexities of O(1) with the hash degrading to a O(n) as collisions increase. That said, I'd go with the trie.
A ternary search tree has lookup times O(log n) character comparisons whereas a bst has lookup times O(log n) actual full key comparisons so they are no where near as slow as bsts. According to Dr. Dobbs Journal (link provided in my last post) real world performance for insertions and successful lookups is roughly equivalent to a hash table, but it offers these benefits:
Ternary trees are usually substantially faster than hashing for unsuccessful searches.
Ternary trees gracefully grow and shrink; hash tables need to be rebuilt after large size changes.
Ternary trees support advanced searches, such as partial-match and near-neighbor search.
Ternary trees support many other operations, such as traversal to report items in sorted order.
They also use substantially less storage than an array trie (9 times less according to this paper:
http://users.info.unicaen.fr/~daireaux/ANADY/PUBLIS/ClementFlajoletVallee2.ps.gz) and will probably achieve better cache utilization as a result.
