Crit bit tree

Crit bit trees can be thought of as a generalization of Binary decision diagrams used to implement a bag or a mapping from keys to values. To implement a bag, the consecutive bits of the value being inserted/removed, and the BDD evaluates to 1 iff the value is in the bag. To implement a mapping from keys to values, simply concatenate the bits of the key and value; to retrieve a given key, follow the BDD tree according to the bits of the key, and then take any path down the tree (recording bits as you go) which does not lead directly to 0 (if only one value is stored for a given key, there will be only one path).

The concept was introduced in 1968 as "Patricia_tries", and independently by Gwehenberger around the same time.

Comparison to other Data Structures

In the following comparisons, it is assumed that the keys are of length "k" and the data structure contains "n" elements. Although k is bounded by $k<\log _{2}n$, this bound is generally not assumed to be tight; if it were, then Hash tables would require O(log n) rather than the generally accepted O(1), since one must touch every bit of a key in order to hash it.

Comparison to Balanced Trees

Like balanced trees, crit bit trees support finding the lexographic successor/predecessor in O(1). Unlike balanced trees, crit bit trees permit lookup, insertion, and deletion in O(k) time rather than O(log n).

Despite their advantages, crit bit trees can only be used with keys for which there exists a bijection to the set of bit strings. In other words, balanced trees can be keyed on any domain for which there exists a total ordering and greater-than/less-than operation.

Comparison to Hash Tables

Like hash tables, Crit Bit Trees support O(k) insertion and deletion, but also permit O(1) successor/predecessor operations. Furthermore, the O(k) bound on crit bit trees is a worst-case bound rather than an average-case bound (as in hash tables).

External Resources

Dan Bernstein's page on Crit Bit Trees