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.