The Van Emde Boas Tree

An ordered set stores keys while supporting queries such as membership, minimum, maximum, predecessor, and successor. The predecessor of 10 in {2, 3, 7, 14} is 7: the largest stored key smaller than 10.

A comparison-based balanced tree such as a splay tree or randomized treap expresses its cost in terms of the number of stored keys. A van Emde Boas tree instead uses the binary representation of bounded integer keys to obtain a bound in terms of the universe.

A van Emde Boas tree operates on integers from a fixed universe {0, …, U − 1}. The direct construction is simplest when U is a power of two whose exponent is also a power of two. Other bounded universes can be rounded up.

The structure depends on the universe size rather than only the number of stored keys. This assumption permits direct addressing and constant-time decomposition of a key into bit fields.

Each node divides its universe into approximately √U clusters, each covering approximately √U consecutive values. For U = 16, cluster 0 covers 0–3, cluster 1 covers 4–7, cluster 2 covers 8–11, and cluster 3 covers 12–15.

Every cluster is another van Emde Boas tree over its local offsets. Recursion therefore reduces a universe of size U to one of size √U.

Two functions locate a key. high(x) selects its cluster, while low(x) selects its offset inside that cluster. With U = 16, high(13) = 3 and low(13) = 1.

The inverse operation combines a cluster number and local offset: index(h, l) = h · √U + l. With power-of-two universe sizes, shifts and masks implement these operations in constant time.

A non-base node contains four kinds of state: min, max, one recursive summary, and an array of recursive cluster structures. The summary and every cluster operate on universes of size approximately √U.

The clusters partition possible key values, while the summary orders the clusters that currently contain data. This two-level representation repeats at every recursive level.

A node also contains a recursive summary over its cluster numbers. Summary key i is present exactly when cluster i is non-empty.

The summary avoids scanning empty clusters. A query that exhausts one cluster asks the summary for the next or previous non-empty cluster, then continues from that cluster’s minimum or maximum.

Recursion stops when U = 2, where the only possible keys are 0 and 1. Membership, insertion, deletion, predecessor, and successor can then be handled with explicit constant-size cases.

This base case is essential to the recurrence. Each higher node reduces its key width before delegating, and no recursive allocation is needed once only two positions remain.

Each node stores its minimum and maximum explicitly. Reading either value takes constant time, including at the root.

In the standard optimized construction, the minimum is held outside the recursive clusters. The first insertion into an empty node sets both extrema without descending, which keeps an update to one nontrivial recursive call per level.

Membership first compares the query with the node’s stored minimum and maximum. If neither matches and U > 2, compute high(x) and recursively search that cluster for low(x).

For key 7 in a universe of 16, high(7) = 1 and low(7) = 3. The root therefore asks cluster 1 whether it contains local key 3. Only one cluster is visited at each level.

To find successor(x), first check whether x is below the node’s minimum. Otherwise inspect cluster[high(x)]. If that cluster contains a value larger than low(x), recurse within it and recombine the result.

For S = {2, 3, 7, 14}, successor(8) begins in cluster 2, which is empty. The summary reports that cluster 3 is the next non-empty cluster. Its local minimum is 2, so index(3, 2) = 14.

If the local cluster has no larger value, this summary transition replaces a linear scan across clusters. Predecessor is symmetric: use local maxima and ask the summary for the previous non-empty cluster.

An insertion into an empty node initializes its minimum and maximum. Otherwise, if the new key is smaller than the current minimum, exchange the two so the stored minimum remains outside the clusters.

When the target cluster is empty, insert its number into the summary and initialize the cluster directly. When it is non-empty, recurse only into that cluster. Finally update the node’s maximum if required.

Deleting the only stored key empties the node. If the deleted key is the minimum and other keys remain, the summary identifies the first non-empty cluster; that cluster’s minimum becomes the new global minimum.

After deleting from a cluster, an empty cluster must also be removed from the summary. The maximum is repaired from the last non-empty cluster when necessary. These cases preserve the summary invariant and the explicit extrema.

Each nontrivial operation performs constant work and makes one recursive call on a universe of size √U. Its recurrence is T(U) = T(√U) + O(1).

Repeated square roots reach the constant-size base case after O(log log U) levels. Membership, insertion, deletion, predecessor, and successor therefore have O(log log U) worst-case time in the direct structure.

Let the universe contain all w-bit integers, so U = 2^w. Then log log U = log w. A 64-bit universe gives only a logarithmic number of recursive levels in the word width.

This analysis assumes a word-RAM that stores a key in one machine word and performs shifts, masks, arithmetic, and addressed memory access in constant time. It does not apply to arbitrary-length keys under a comparison-only model.

The direct recursive layout allocates clusters according to the universe. Its space recurrence produces O(U) space even when only n keys are stored.

This is the principal limitation. A direct structure for a small dense universe can be reasonable; allocating around a sparse 32-bit or 64-bit universe is not. Pointer overhead and weak cache locality add practical costs beyond the asymptotic bound.

Hashing can create recursive clusters only when they become non-empty, reducing the occupied structure. Related integer dictionaries use the same universe-reduction principle with different representations.

Willard’s y-fast trie combines sampled prefixes with balanced groups to achieve linear space and doubly logarithmic predecessor queries. Modern engineered predecessor sets similarly combine universe reduction, hashing, and compact representations for small subproblems.

The original structure was presented as a priority queue for bounded integer priorities. A concrete modern use appears in Gallatin, an open-source CUDA memory allocator. Gallatin partitions GPU memory into numbered segments and keeps their availability in vEB trees. Successor search selects the lowest available segment at or beyond a requested position, helping the allocator reuse memory while limiting fragmentation.

Gallatin adapts the design for GPU concurrency: its nodes use compact bit summaries and atomic operations rather than reproducing the pointer-heavy textbook structure unchanged. This distinction is representative. Direct vEB implementations are uncommon in general-purpose libraries because O(U) allocation and pointer chasing can outweigh the small recursion depth. A vEB tree is most attractive when the universe is bounded and sufficiently dense and predecessor or successor queries dominate; self-adjusting trees, randomized search trees, sorted arrays, radix structures, or y-fast tries are often preferable when space, cache behavior, iteration, or sparse keys matter more.

A van Emde Boas tree partitions a bounded integer universe into square-root clusters and recursively summarizes which clusters are non-empty. Explicit minima and maxima make extrema constant-time and keep each update to one nontrivial recursive branch per level.

The direct structure supports membership, insertion, deletion, predecessor, and successor in O(log log U) worst-case time with O(U) space. Its speed comes from operating on fixed-width integer representations rather than treating keys as comparison-only objects.