D. J. Bernstein
Data structures and program structures

Crit-bit trees

Interface to crit-bit trees

A crit-bit tree stores a prefix-free set of bit strings: a set of 64-bit integers, for example, or a set of variable-length 0-terminated byte strings.

A crit-bit tree supports the following operations (and more!) at high speed:

A crit-bit tree can be used as a high-speed associative array. For example, an array mapping 54 to 1, 19 to 2, 99 to 3, 85 to 4, and 88 to 5 can be stored as a crit-bit tree containing 54=1, 19=2, 99=3, 85=4, and 88=5. The smallest string in the crit-bit tree larger than 85= is 85=4.

Definition of crit-bit trees

A crit-bit tree for a nonempty prefix-free set S of bit strings has an external node for each string in S; an internal node for each bit string x such that x0 and x1 are prefixes of strings in S; and ancestors defined by prefixes. The internal node for x is compressed: one simply stores the length of x, identifying the position of the critical bit (crit bit) that follows x.

Each internal node in a pure crit-bit tree is stored as three components:

The total overhead, on top of the strings stored, is one pointer down to each internal node, and one integer at each internal node; in other words, one pointer and one integer for each string.

Strings need to be visibly distinguishable from pointers, but this costs at most one extra bit per string. The simplest general approach is to incorporate these two internal/external selector bits into the length, to have the left string stretching out to the left of the length in memory, and to have the right string stretching out to the right of the length in memory; all of the usual string-termination options, including counters and 0-termination and known fixed lengths, are applicable. Of course, pointing to this node means pointing to the length field in the middle. If strings are actually expressed as pointers to a separate storage pool, with at least 2-byte alignment for each pointer, then another option is to use the bottom bit of the pointer as the internal/external selector bit.

Variants of crit-bit trees

People are often tempted to augment the internal nodes in binary trees to include parent pointers, sibling pointers, child counts, etc. However, these modifications consume more space than a pure crit-bit tree, and I haven't seen any serious applications where the modifications provide speedups that outweigh the general slowdown caused by using more memory.

The basic idea of critical bits was introduced in 1968 by Morrison and independently Gwehenberger, but in retrospect their data structures were unnecessarily augmented beyond pure crit-bit trees. Subsequent variants differ in the amount of augmentation, in the algorithms provided, and in the correctness of those algorithms:
Overhead on top of each string storedLiterature
5 control words: pointer, pointer, pointer, integer, integer1968 Morrison; "PATRICIA"; no mention that fast deletion is possible
3 control words: pointer, pointer, integer1968 Gwehenberger; no mention that fast deletion is possible
4 control words: pointer, pointer, pointer, integer1973 Knuth; algorithms provided for suffix searching and (in an exercise) insertion; no mention of fast deletion and lexicographic operations
3 control words: pointer, pointer, integer1983 Sedgewick; mentions that deletion is possible but does not state a deletion algorithm; at least in the first two editions, states an insertion algorithm that fails when it inserts a new root (pointed out by Tim Lee)
3 control words: pointer, pointer, integer1991 Sklower; only for short fixed-length strings; implementations of insertion, deletion, and lexicographic searching
2 control words: pointer, integer2004 Bernstein; "crit-bit trees"; implementations (posted in 2006) of insertion, deletion, exact searching, and suffix searching

Most people don't seem to realize how fast crit-bit trees can be; most people don't seem to realize how small crit-bit trees can be; most people don't seem to realize that crit-bit trees support all of the standard data-structure operations. PATRICIA is often dismissed as being large and complicated, but pure crit-bit trees are actually quite small and simple.

Putting crit-bit trees to work

The standard strategy for many years has been to store searchable data sets as hash tables, in applications that need exact searches but not lexicographic searches; or as heaps, in applications that need to search for the minimum; or as AVL trees, red-black trees, etc. in applications that do not fit the restrictions of hash tables and heaps.

In Python, for example, the built-in "dict" data type is a hash table. Hash tables don't provide fast access to the smallest entry, so there's also a standard "heapq" library providing heaps. Heaps don't provide fast lookups of other entries, so there are various add-on libraries providing AVL trees and so on. A programmer who's happy creating a "dict" will simply do so, but then another programmer who wants fancier operations on the resulting database has to do an expensive conversion of the "dict" to a fancier data structure.

I have become convinced that this strategy should change. The revised strategy is much simpler: there should be one fundamental set-storage type, namely a crit-bit tree. Here's how a crit-bit tree stacks up against the competition:

If you're designing a programming language, imagine how much happier your programmers will be if your basic built-in data type allows not just looking up x, but also enumerating the strings after x in sorted order. You can't do this with hash tables. You could do it with an AVL tree, but your operations will be simpler and faster if you use a crit-bit tree.