Ternary Search Trees

[Robert Fraser]

bearophile wrote:
> Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
> TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
> They can be designed to store the keys alone, or as an associative data structure.
> 
> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
> 
> Bye,
> bearophile

I'd love to see them! Got a Tango version? ;-P

Also, D's AAs aren't a great benchmark, since they are outperformed by 
even a basic hashtable implementation (compare them to 
tango.util.collection.HashMap). But TSTs support many more operations, 
so the fact that they're slower than BSTs/Hashtables is to be expected.