Ternary Search Trees

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Wed Apr 15 21:36:01 PDT 2009


Robert Fraser wrote:
> 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
> 
> Hey, could you please post your implementation (assuming it's 
> open-source?) I'd love to use them, but can't be bothered to implement 
> it. Thanks!

BTW, anyone got a KD-tree implementation? I could use one.

Andrei



More information about the Digitalmars-d mailing list