Skip to content
Tutorials Center
My learning

Topics

Lesson 207 of 225 ยท Advanced Topics

van Emde Boas Trees and Y-fast Tries

Learn how van Emde Boas trees find successors and predecessors of integer keys in O(log log u), build one in Python, and see how Y-fast tries save space.

A balanced search tree finds the successor of a key in O(log n). For arbitrary comparable data, that is the best you can do with comparisons alone. But if your keys are integers from a small universe 0 .. u-1 (port numbers, minutes in a day, 32-bit IP addresses), you can exploit the bits of the key and go faster: the van Emde Boas tree (vEB) supports insert, delete, membership, minimum, maximum, successor and predecessor in O(log log u) time. For u = 2^32, that is about 5 steps, since log2(32) = 5.

The price is space: a plain vEB tree uses O(u) memory, which is huge for a sparse set. The Y-fast trie repairs that, reaching O(n) space. This lesson builds the idea from arrays of bits, implements a working vEB tree in Python, and explains Y-fast tries conceptually. It is an advanced topic, so it helps to know balanced trees, tries and priority queues.

The recursive square-root split

Imagine a universe of u = 16. A bit array of 16 flags answers membership in O(1), but finding the successor means scanning up to 16 cells. Split the universe into 4 clusters of 4 keys each. A key x lives in cluster high(x) = x // 4 at position low(x) = x % 4. In terms of bits, high is the upper half of the bits of x and low is the lower half.

Add one more structure: a summary that records which clusters are non-empty. To find the successor of x, first look inside its own cluster; if nothing larger is there, ask the summary for the next non-empty cluster and take that cluster's minimum.

flowchart TD
    V["vEB(16)<br/>min, max"] --> SUM["summary vEB(4)<br/>which clusters are non-empty"]
    V --> C0["cluster 0<br/>vEB(4): keys 0-3"]
    V --> C1["cluster 1<br/>vEB(4): keys 4-7"]
    V --> C2["cluster 2<br/>vEB(4): keys 8-11"]
    V --> C3["cluster 3<br/>vEB(4): keys 12-15"]

A vEB tree over 16 keys: four clusters and a summary, each a smaller vEB tree over the square root of the universe.

The clusters and the summary are themselves vEB trees over a universe of size sqrt(u), so the structure is recursive. The universe size goes u -> sqrt(u) -> u^(1/4) -> ..., which takes only log log u levels to reach 2.

Why only one recursive call?

Naively, a successor query might recurse twice (into the cluster, then into the summary), giving T(u) = 2T(sqrt u) + O(1) = O(log u), no better than a binary search tree. The vEB trick makes sure that at most one recursive call does real work:

  • Each node stores its min and max outside the recursion. The minimum is not stored again inside a cluster.
  • Checking whether a cluster has a larger element than low(x) is a comparison with the cluster's max, which costs O(1).
  • Inserting into an empty cluster is O(1) (just set min and max), so only the summary insert recurses; inserting into a non-empty cluster does not touch the summary.

That gives T(u) = T(sqrt u) + O(1), which solves to O(log log u).

flowchart TD
    A["successor(x)"] --> B{"x below min?"}
    B -- yes --> C["return min"]
    B -- no --> D{"low(x) below max<br/>of its cluster?"}
    D -- yes --> E["recurse inside the cluster"]
    D -- no --> F["ask summary for next<br/>non-empty cluster"]
    F --> G["return that cluster's min"]

Exactly one of the two branches recurses, which is what makes it O(log log u).

Implementation

We handle universes of size 2^k. For a node of k bits, the low half has k // 2 bits and the high half the rest. Clusters are created lazily in a dictionary, so unused parts cost nothing in this implementation (a classic array-based version always allocates everything).

Python A van Emde Boas tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice what the insert method does when the new key is smaller than the stored minimum: it swaps them, and the old minimum is the one pushed down into a cluster. That is how the minimum stays outside the recursion.

Checking it against a sorted list

Never trust a tricky structure without a test. This program inserts random-looking keys with a fixed generator and compares every successor and predecessor answer with bisect on a sorted list.

Python Cross-check against bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Zero mismatches means the successor and predecessor logic, including the lazily created summary, agrees with the reference.

Deletion and space

Deletion mirrors insertion: if the key being deleted is the minimum, pull the next smallest key out of the first non-empty cluster to become the new minimum; if its cluster becomes empty, remove the cluster from the summary. Again only one of the two branches recurses. We leave the code as an exercise because it adds many edge cases but no new idea.

The weakness is space. A vEB tree over u keys needs Theta(u) memory when built with arrays, even if it holds only ten keys. With u = 2^32 that is far too much, and even the lazy dictionary version above can allocate many small nodes.

Y-fast tries: the same speed in O(n) space

A Y-fast trie combines two ideas to get O(n) space while keeping O(log log u) time (the updates are amortized, and a randomized hash table is used):

  1. X-fast trie on a few representatives. An x-fast trie stores every prefix of every key in hash tables, one per bit level. To find the successor, binary search over the length of the matching prefix (log u levels, so O(log log u) hash lookups). It needs O(n log u) space, which is too much for all keys.
  2. Buckets of size about log u. Sort the keys and cut them into groups of Theta(log u) consecutive keys, each stored in a small balanced tree. Only one representative per group goes into the x-fast trie, so the trie holds n / log u keys and takes O(n) space.

A query finds the right group through the x-fast trie in O(log log u), then searches the small group in O(log log u) (a tree of log u elements is log log u deep).

flowchart TD
    Q["Query x"] --> X["X-fast trie of representatives<br/>binary search on prefix length<br/>O(log log u)"]
    X --> G["Bucket of about log u keys<br/>balanced tree<br/>O(log log u)"]
    G --> R["Successor of x"]

A Y-fast trie: a sparse x-fast trie routes the query to a small bucket.

We cannot build a full x-fast trie in a few lines, but the following program shows the bucket idea. A sorted list of representatives (standing in for the x-fast trie, using bisect instead of prefix hashing) routes each query to a small sorted bucket.

Python The bucket idea behind Y-fast tries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When is this actually used?

In practice, vEB trees are rarely the fastest option: their constants are large and bit-level tricks or a plain B-tree or sorted array often win for real data. Their importance is theoretical and educational: they show how breaking the comparison model by using the key's bits beats O(log n), and the same recursive-universe idea appears in IP routing tables, integer sorting bounds and some priority queue designs. Simpler cousins such as a Fenwick tree with bit descent or a 64-ary bitset tree solve many practical successor problems with less code.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the time for successor in a van Emde Boas tree over a universe of size u?

    The universe size shrinks from u to sqrt(u) at each level and only one recursive call does real work, giving T(u) = T(sqrt u) + O(1) = O(log log u).
  2. 2. Why does a vEB node store its minimum outside the clusters?

    Because min is stored only at the node, inserting into an empty cluster stops immediately, so insert and successor never need two expensive recursive calls.
  3. 3. What is the main drawback of a plain array-based vEB tree?

    The clusters and summaries cover the whole universe, so memory grows with u, not with the number of stored keys.
  4. 4. How does a Y-fast trie reach O(n) space?

    The x-fast trie costs O(log u) space per key, but it only holds n / log u representatives, and the buckets use O(n) in total.

Summary

  • vEB trees speed up ordered-set operations on integer keys from a universe of size u to O(log log u).
  • They split each key into high and low halves, keep a summary of non-empty clusters, and store min/max outside the recursion so that only one recursive call is needed.
  • Array-based vEB trees use O(u) space; the Y-fast trie fixes that with an x-fast trie of representatives and small bucket trees, giving O(n) space.
  • In practice, B-trees and bitset trees are often faster, but the ideas are central to integer data structures.

Next: Project: Autocomplete