X-fast trie

In computer science, an x-fast trie is a data structure for storing integers from a bounded domain.

Each leaf stores a pointer to its predecessor and successor, thereby forming a doubly linked list.

Like van Emde Boas trees, x-fast tries support the operations of an ordered associative array.

This includes the usual associative array operations, along with two more order operations, Successor and Predecessor: Finding the value associated with a key k that is in the data structure can be done in constant time by looking up k in LSS[0], which is a hash table on all the leaves.

Therefore, the descendant pointer points to the successor or the predecessor of k. Depending on which one we are looking for, we might have to take one step in the linked list to the next or previous leaf.

Then we walk from the leaf to the root of the trie, removing all nodes whose subtree only contained k and updating the descendant pointers where necessary.

[1] A compression technique similar to patricia tries can be used to significantly reduce the space usage of x-fast tries in practice.

A binary tree with 4 levels. The nodes on each level are: 3: (), 2: (0) and (1), 1: (00) and (10), 0: (001), (100) and (101). The unlabeled node is the root. There are directed edges between the following nodes: ()->(0), ()->(1), (0)->(00), (0)->(100) in blue, (1)->(10), (1)->(101) in blue, (00)->(001) twice, once in blue, (10)->(100), (10)->(101), (001)<->(100), (100)<->(101). The nodes on each level are contained in a box, labeled with LSS(<level>).
An x-fast trie containing the integers 1 (001 2 ), 4 (100 2 ) and 5 (101 2 ). Blue edges indicate descendant pointers.