Subj : Ternary (Unary) Seach Tree
To   : comp.programming
From : Gabriel
Date : Wed Aug 24 2005 05:20 am

Hi!

I'm experimenting with search trees. Namely,  ternary search tree,
based on Bentley&Sedgewick's algorithm. But the tree is very sparse and
has lots of null pointers, that I'd like to avoid. I impoved my
implementation adding suffix compaction to the tree. It's now less
readable. And the suffixes shrink as new strings with same prefixes are
added to it. My point is to make a tree (dictionary) I can insert into
(delete from) and use space efficiently without loosing all the
advantages of TST.

I read in Phill Bagwell's paper Fast And Space Efficient Trie Searches
about Unary Search Trees. But the idea behind the data structure isn't
clear to me. Could anyone be so kind and shed a light on this topic for
me. A small tree, with explanation would be very helpfull.

Thanks,

Gabriel

.