Crit-bit trees (29 Sep 2008)
I wrote up djb's implementation of crit-bit trees for strings here [pdf]. Crit-bit trees have several nice properties:
- Fast: only a single string compare per lookup.
- For finite sets (like 32-bit ints) the depth of the tree is bounded by the length of the longest element.
- Simple code - no complex balancing operations
- Supports the usual tree operations: successor, minimum, prefix set etc.