Y-Fast Trie

Y-fast trie is a hierarchical bitwise ordered dictionary data structure within computation and algorithms that maintains a dynamic set of n integers drawn from a bounded universe {0, 1, …, U − 1} in linear O(n) space while executing search, predecessor, successor, insertion, and deletion operations in O(log log U) time on a Word RAM processor. Introduced by American computer scientist Dan E. Willard in 1983, the structure resolves the primary memory bottleneck of the van Emde Boas tree, which requires O(U) pointers regardless of how few keys are actually stored.

When integer keys have word length w = log₂ U bits, standard comparison-based balanced trees such as red-black trees and splay trees require Θ(log n) comparisons per query. Willard achieved doubly logarithmic O(log w) = O(log log U) lookup time in two stages: first constructing the X-fast trie, which applies binary search over prefix lengths using level hash tables in O(n log U) space, and then compressing that space by a factor of Θ(log U) via two-level tree indirection to form the Y-fast trie.

Bitwise Prefix Trie With Level Hash Tables

To understand the top tier of a Y-fast trie, consider first an X-fast trie storing a set S of n integer keys in {0, 1, …, 2^w − 1}. Conceptually, an X-fast trie is a binary trie of height w in which each key x ∈ S corresponds to a root-to-leaf path of length w determined by its binary representation b_w−1b_w−2…b₀ from most significant bit to least significant bit. An internal node at depth d ∈ {0, 1, …, w} represents the d-bit binary prefix ⌊x / 2^w−d⌋ of all keys in its subtree, while the leaves at depth w store the elements of S in sorted order linked inside a doubly linked list.

Traversing this binary trie top-down bit by bit would require O(w) = O(log U) steps. To accelerate traversal to O(log w) = O(log log U) time, an X-fast trie augments the tree with two auxiliary mechanisms:

1. Level Search Table (LST): An array of w + 1 hash tables H₀, H₁, …, H_w, where table H_d stores all existing internal trie nodes at depth d indexed by their d-bit prefix integer value. Using dynamic perfect hashing (Fredman, Komlós, and Szemerédi, 1984) or cuckoo hashing, checking whether any key in S shares the d-bit prefix of a query integer q takes O(1) time.
2. Descendant Threads (Thread Pointers): If an internal trie node u at depth d lacks a left child (meaning no key in its subtree has bit 0 at position w − 1 − d), its empty left pointer is replaced by a descendant thread pointing directly to the minimum leaf in u's right subtree (the smallest key in S bearing prefix u). Symmetrically, if u lacks a right child, its empty right pointer threads directly to the maximum leaf in u's left subtree (the largest key in S bearing prefix u). Because every existing internal node has at least one child, it lacks at most one child, so every leaf boundary below u is reachable in O(1) time once u is located.

Binary Search Over Prefix Lengths

Given a query integer q ∈ {0, 1, …, U − 1}, the longest common prefix between q and the stored set S corresponds to the deepest ancestor node along q's root-to-leaf path that exists in the X-fast trie. Because the existence of prefixes of q is monotone with respect to depth—if the prefix of length d exists in H_d, then every shorter prefix of length d' < d also exists in H_d'—an X-fast trie locates the deepest existing ancestor u* of q by performing binary search over the depth parameter d ∈ {0, 1, …, w}:

• At each step of the binary search, probe H_m for the m-bit prefix ⌊q / 2^w−m⌋ in O(1) time.
• If the prefix exists in H_m, search the deeper half [m, high]; otherwise, search the shallower half [low, m − 1].

After ⌈log₂(w + 1)⌉ = O(log w) = O(log log U) hash lookups, the algorithm identifies the deepest matching node u* at depth d. Depending on the next bit of q, following the missing child's descendant thread from u jumps in O(1) time to either the predecessor leaf pred(q) or the successor leaf succ(q) in the doubly linked list at the bottom of the trie.

Bucketing Keys Into Balanced Binary Search Trees

Although an X-fast trie achieves O(log log U) predecessor queries, each of the n keys generates up to w = log₂ U prefix entries across the level hash tables H₁, …, H_w, consuming O(n log U) words of memory and requiring O(log U) ancestor pointer updates per insertion or deletion.

A Y-fast trie eliminates this logarithmic factor in both space and update time by partitioning the sorted key set S into contiguous buckets (clusters) of size Θ(log U) = Θ(w):

1. Bottom-Level Balanced BST Buckets: The n elements of S are partitioned into k = Θ(n / log U) disjoint contiguous intervals B₁ < B₂ < … < B_k. During dynamic updates, each bucket B_i is maintained so that its cardinality satisfies the capacity invariant (1/4) log₂ U ≤ |B_i| ≤ 2 log₂ U. Every bucket B_i is stored as a standard balanced binary search tree—such as a red-black tree, AVL tree, or treap—which occupies O(|B_i|) space and supports search, insertion, deletion, split, and join in O(log |B_i|) = O(log log U) time.
2. Top-Level X-Fast Trie Over Representative Splitters: For each bucket B_i, one representative key r_i (chosen from the interval between max(B_i−1) + 1 and min(B_i+1) − 1, initially set to max(B_i)) is inserted into a top-level X-fast trie T_top, along with a pointer from the leaf r_i to the root of the balanced binary search tree for B_i.

Because T_top stores only k = O(n / log U) representative keys, the total memory consumed by the top-level X-fast trie and its w level hash tables is:

Combined with the O(n) total nodes across all bottom-level balanced binary search trees, the complete Y-fast trie uses linear O(n) words of memory.

Predecessor and Successor Queries in O(log log U) Time

To find Predecessor(q) or Successor(q) for a query integer q:

1. Query the top-level X-fast trie T_top for the smallest representative r_i ≥ q and the adjacent representative r_i−1 (or r_i+1) in O(log log U) time.
2. Because representative keys may drift slightly from the current maximum of their bucket during deletions without triggering a top-level update, the true predecessor and successor of q must reside inside at most two adjacent buckets: B_i−1, B_i, or B_i+1.
3. Search those two bottom-level balanced binary search trees of size O(log U). Because searching a balanced binary search tree of M = Θ(log U) nodes requires O(log M) = O(log log U) comparisons, the entire query finishes in O(log log U) worst-case time.

Bucket Splitting, Merging, and Amortized Cost Analysis

When inserting a new key x into the Y-fast trie, the algorithm first locates the target bucket B_i via T_top in O(log log U) time and inserts x into the balanced binary search tree of B_i in O(log log U) time. As long as the size of B_i remains within [(1/4) log₂ U, 2 log₂ U], the top-level X-fast trie T_top is untouched!

• Bucket Overflow Split (|B_i| > 2 log₂ U): When a bucket exceeds 2 log₂ U keys, its balanced binary search tree is split around its median in O(log log U) time into two buckets B' and B'' of size log₂ U each, and one new representative key is inserted into the top-level X-fast trie T_top at a cost of O(log U) hash table updates.
• Bucket Underflow Merge (|B_i| < (1/4) log₂ U): When deletions shrink a bucket below (1/4) log₂ U keys, it is merged with an adjacent bucket B_i+1. If the combined bucket exceeds (3/2) log₂ U keys, it is immediately re-split into two balanced halves of size ≈ (3/4) log₂ U. Updating T_top costs O(log U) time.

Because any newly split or re-balanced bucket has size between (1/2) log₂ U and (3/2) log₂ U, at least Ω(log U) subsequent insertions or deletions must occur inside that bucket before it can overflow above 2 log₂ U or underflow below (1/4) log₂ U again. Charging the O(log U) top-level X-fast trie reconstruction cost across those Ω(log U) bottom-level updates yields an amortized update cost of:

High-Speed IP Prefix Lookup and Interval Geometry

In network packet classification and orthogonal computational geometry, dynamic point location along a coordinate axis of resolution U = 2³² or 2⁶⁴ reduces directly to dynamic predecessor search. Whereas a segment tree over universe U requires O(log U) traversal depth, replacing coordinate binary search with a Y-fast trie reduces orthogonal range reporting, stab queries, and sweeping-line active interval lookups from O(log n) to O(log log U) in linear space. In main-memory database indexing, Y-fast trie principles inform hybrid radix-tree and B-tree indexes that index high-order bits via hash or radix tables while storing dense key clusters in cache-resident search trees.

How does a Y-fast trie compare to a hash-backed van Emde Boas tree?

Both a Y-fast trie and a hash-table-backed van Emde Boas tree achieve O(n) space and O(log log U) query and expected update times. However, a hash-backed vEB tree distributes hash tables across log₂ log₂ U recursive levels of varying integer widths and requires recursive pointer chasing at every query step. By contrast, a Y-fast trie performs its hash probes non-recursively inside a single flat X-fast trie containing only O(n / log U) elements, and handles 1 − O(1 / log U) of all insertions and deletions inside cache-friendly bottom-level balanced binary search trees without touching any hash table at all.

Can the amortized update bound of a Y-fast trie be de-amortized to worst-case time?

Yes. By applying incremental background rebuilding (spreading the O(log U) X-fast trie insertion or deletion steps across the next (1/8) log₂ U updates hitting that bucket, performing O(1) hash-level pointer updates per operation) combined with deterministic dynamic dictionaries at the trie levels, Willard (1983) and subsequent authors showed that updates can be executed in O(log log U) worst-case or high-probability time.

When is a comparison-based tree faster than a Y-fast trie?

When the number of stored elements n is small enough that log₂ n ≤ log₂ log₂ U (for instance, n ≤ 64 for 64-bit keys), or when keys are variable-length strings rather than bounded machine words, a standard balanced binary search tree or B-tree avoids hashing overhead and achieves lower constant factors. Y-fast tries excel when n is large (such as millions of 32-bit or 64-bit integers) so that log₂ log₂ U ∈ {5, 6} is substantially smaller than log₂ n ≥ 20.

1. Willard, D. E. (1983). "Log-logarithmic worst-case range queries are possible in space Θ(N)." Information Processing Letters, 17(2), 81–84. https://doi.org/10.1016/0020-0190(83)90075-390075-3)
2. van Emde Boas, P., Kaas, R., & Zijlstra, E. (1977). "Design and implementation of an efficient priority queue." Mathematical Systems Theory, 10(1), 99–127. https://doi.org/10.1007/BF01683268
3. Fredman, M. L., Komlós, J., & Szemerédi, E. (1984). "Storing a sparse table with O(1) worst case access time." Journal of the ACM, 31(3), 538–544. https://doi.org/10.1145/828.1884
4. Pătraşcu, M., & Thorup, M. (2006). "Time-space trade-offs for predecessor search." In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC '06), 232–240. https://doi.org/10.1145/1132516.1132551