van Emde Boas Tree, in depth: the sqrt(u) recursion, lazy minimum, a tested implementation and when bitmaps win

The recursion behind log log u

Suppose u = 2^k. Write each key as two halves: the high bits pick one of about sqrt(u) clusters, and the low bits give the position inside that cluster. With u = 2^16, the key 0x3A7F has high part 0x3A (cluster 58) and low part 0x7F (offset 127). Each cluster is itself a vEB tree over a universe of size sqrt(u). A separate vEB tree called the summary, also over sqrt(u), records which clusters are non-empty.

To find the successor of x, there are only two cases. If the answer lies in x's own cluster, recurse into that cluster. Otherwise ask the summary for the next non-empty cluster and take its minimum. Because every structure stores its minimum and maximum directly, choosing the case and reading that minimum need no recursion, so each operation makes one recursive call on a universe of size sqrt(u):

T(u) = T(sqrt(u)) + O(1)
let u = 2^k:   S(k) = S(k/2) + O(1)   =>   S(k) = O(log k) = O(log log u)

Halving the bits per level gives log k levels: 32, 16, 8, 4, 2 for 32-bit keys.

The lazy minimum: why insert and delete stay fast

The second idea makes insert and delete as fast as successor. The minimum of a vEB tree is stored only in its min field and is not inserted into any cluster. That has two consequences:

• Inserting into an empty tree is O(1): set min = max = x and stop.
• An insert into an empty cluster recurses only into the summary, because filling the empty cluster is O(1). An insert into a non-empty cluster recurses only into that cluster, because the summary already knows it. Either way, one recursive call.
• A key smaller than the minimum swaps with it, and the old minimum is pushed down instead.

Delete reverses this. Deleting the minimum promotes the smallest clustered element (an O(1) read of summary.min and that cluster's min) and deletes it from its cluster. If the cluster empties, that delete was O(1), so the one real recursion goes to the summary.

Worked example: u = 16

Take u = 16 (4-bit keys, so 2 high bits and 2 low bits: 4 clusters of size 4) and insert 2, 3, 4, 5, 7, 14, 15.

The summary holds {0, 1, 3}. Cluster 2 was never allocated. Now trace three queries.

1. successor(5): high 1, low 1. Cluster 1's max is offset 3, which is greater than 1, so the answer is in this cluster. Recurse to get offset 3, and combine: 1 * 4 + 3 = 7.
2. successor(7): high 1, low 3. Cluster 1's max is also 3, so nothing in this cluster is larger. Ask the summary for the successor of 1, which is 3. Cluster 3's min is offset 2, so the answer is 3 * 4 + 2 = 14.
3. predecessor(3): high 0, low 3. Cluster 0's min is 3, so nothing smaller is in this cluster, and the summary has no cluster before 0. The answer is the top-level min, 2, which never lived in a cluster. Missing this check is the classic bug.

A tested implementation

This implementation allocates clusters lazily in a dictionary, so only non-empty clusters exist. It handles any power-of-two universe, including odd bit counts, where the cluster count and cluster size differ. It was checked against a sorted-list reference with random inserts, deletes and queries for universes from 2 to 2^16.

class VEB:
    """van Emde Boas set over the universe {0, ..., u-1}; u must be a power of two >= 2."""

    def __init__(self, u):
        self.u = u
        self.min = None          # stored here only, never inside a cluster
        self.max = None
        if u > 2:
            k = u.bit_length() - 1
            self.lo_bits = k // 2                 # cluster universe = 2**floor(k/2)
            self.lo_size = 1 << self.lo_bits
            self.hi_size = 1 << (k - self.lo_bits)  # number of clusters = 2**ceil(k/2)
            self.summary = None                   # VEB(hi_size), created lazily
            self.clusters = {}                    # high -> VEB(lo_size), only non-empty ones

    def high(self, x):  return x >> self.lo_bits
    def low(self, x):   return x & (self.lo_size - 1)
    def index(self, h, l): return (h << self.lo_bits) | l

    def member(self, x):
        if x == self.min or x == self.max:
            return True
        if self.u == 2 or self.min is None:
            return False
        c = self.clusters.get(self.high(x))
        return c is not None and c.member(self.low(x))

    def insert(self, x):
        if self.min is None:
            self.min = self.max = x               # O(1): an empty tree just records x
            return
        if x == self.min:
            return
        if x < self.min:
            x, self.min = self.min, x             # new minimum stays here; push the old one down
        if self.u > 2:
            h, l = self.high(x), self.low(x)
            c = self.clusters.get(h)
            if c is None or c.min is None:
                if c is None:
                    c = self.clusters[h] = VEB(self.lo_size)
                if self.summary is None:
                    self.summary = VEB(self.hi_size)
                self.summary.insert(h)            # the one real recursive call
                c.min = c.max = l                 # O(1) insert into an empty cluster
            else:
                c.insert(l)                       # summary already knows h; recurse once
        if x > self.max:
            self.max = x

    def successor(self, x):
        if self.u == 2:
            return 1 if x == 0 and self.max == 1 else None
        if self.min is not None and x < self.min:
            return self.min
        h, l = self.high(x), self.low(x)
        c = self.clusters.get(h)
        if c is not None and c.max is not None and l < c.max:
            return self.index(h, c.successor(l))  # answer is inside x's own cluster
        nh = self.summary.successor(h) if self.summary is not None else None
        if nh is None:
            return None
        return self.index(nh, self.clusters[nh].min)  # O(1) read of the next cluster's min

    def predecessor(self, x):
        if self.u == 2:
            return 0 if x == 1 and self.min == 0 else None
        if self.max is not None and x > self.max:
            return self.max
        h, l = self.high(x), self.low(x)
        c = self.clusters.get(h)
        if c is not None and c.min is not None and l > c.min:
            return self.index(h, c.predecessor(l))
        ph = self.summary.predecessor(h) if self.summary is not None else None
        if ph is None:
            # the minimum lives outside the clusters, so check it last
            return self.min if self.min is not None and x > self.min else None
        return self.index(ph, self.clusters[ph].max)

    def delete(self, x):
        """Remove x; the caller guarantees x is present (check member() first)."""
        if self.min == self.max:
            self.min = self.max = None
            return
        if self.u == 2:
            self.min = self.max = 1 - x
            return
        if x == self.min:
            # promote the smallest clustered element to be the new minimum
            first = self.summary.min
            x = self.index(first, self.clusters[first].min)
            self.min = x
        h, l = self.high(x), self.low(x)
        c = self.clusters[h]
        c.delete(l)
        if c.min is None:
            del self.clusters[h]
            self.summary.delete(h)
            if x == self.max:
                top = self.summary.max
                self.max = self.min if top is None else self.index(top, self.clusters[top].max)
        elif x == self.max:
            self.max = self.index(h, c.max)

Two contracts matter. delete assumes the key is present, as in the textbook version, so a public wrapper should call member first. And insert ignores duplicates, which makes this a set. For a multiset, keep a count per key in a side dictionary and only touch the tree when a count moves between zero and one.

Space: from O(u) to linear

The textbook version allocates every cluster up front, which costs O(u) space whatever the number of keys. That is fine for u = 2^16, painful for 2^24, and impossible for 64-bit keys. Lazy allocation through a hash map, as above, removes empty clusters. Each insert creates at most one new structure per level, so space is bounded by O(n log log u), at the price of hash lookups on every step and expected rather than worst-case time.

For linear space, Willard's x-fast trie hashes every prefix of every key and binary-searches over prefix length (O(log log u) queries, O(n log u) space). The y-fast trie puts keys in balanced-tree buckets of about log u and stores one representative per bucket in an x-fast trie, reaching O(n) space with amortised expected O(log log u).

Word-sized leaves

Recursing all the way down to u = 2 wastes most of the work, because a machine word can hold a whole 64-element universe as a bitmask. Successor and predecessor within a word take one shift and one count-trailing-zeros or highest-bit instruction. Real implementations stop the recursion at a word:

def word_successor(word, x):
    """Smallest set bit position > x in a 64-bit word, or None."""
    rest = word >> (x + 1) if x < 63 else 0
    if rest == 0:
        return None
    return x + 1 + ((rest & -rest).bit_length() - 1)   # count trailing zeros

def word_predecessor(word, x):
    """Largest set bit position < x in a 64-bit word, or None."""
    rest = word & ((1 << x) - 1)
    return rest.bit_length() - 1 if rest else None

In C or Rust these are __builtin_ctzll or trailing_zeros and their leading-zero equivalents, single instructions on current x86 and ARM cores. The structure then looks like a hierarchical bitmap, which leads to the key practical point.

Hardware reality and where vEB pays off

Asymptotics are not the whole story. Each vEB level is a pointer or hash lookup into a different part of memory, so a query costs a handful of cache misses. A 64-ary bitmap tree (one bit per child, summary words above leaf words) has log_64 u levels: 4 for 24-bit keys, 6 for 32-bit. Each level is a single word read plus a bit instruction, in arrays laid out contiguously. That is O(log u / log w) rather than O(log log u), but for realistic universes it is usually faster, simpler and smaller. For sparse sets of 32-bit integers, compressed bitmaps such as Roaring bitmaps are usually the better engineering choice.

The vEB idea pays off for bounded integer keys, successor-heavy workloads and constantly changing sets:

• monotone integer priority queues, such as Dijkstra's algorithm with small integer edge weights;
• timer and event schedulers keyed by tick;
• allocators that need the next free block at or after an address;
• competitive programming problems with fixed universes.

Benchmark first against binary heaps or a B-tree on your own keys.

Failure modes

• Bad universe or keys. Round u up to a power of two, map signed keys (flip the sign bit), and reject out-of-range keys at the API boundary.
• Forgetting the top-level minimum in predecessor or delete. Randomised tests catch it.
• Deleting an absent key. The textbook delete corrupts min and max. Guard with member.
• Eager allocation exhausting memory at 2^24 and above. Allocate lazily, or use word leaves and arrays.
• Recursion overhead in interpreted languages. In Python, call overhead usually makes bisect on a sorted list faster; write production versions in a compiled language.

Trade-offs

What to do next

1. Type in the class above and run it against a sorted-list reference with random operations for u = 2, 8, 16 and 2^16. The odd exponent of 8 catches split bugs.
2. Trace successor and predecessor by hand on the u = 16 example until the top-level-minimum case feels obvious.
3. Replace the u = 2 base case with a 64-bit word leaf and confirm the tests still pass.
4. Implement a 64-ary bitmap tree for the same interface and benchmark both on your real key distribution.
5. Read about x-fast and y-fast tries to see how hashing removes the dependence on u for space.
6. If you need an integer priority queue, compare against a heap before adopting either structure.

Related: prefix structures in tries are the conceptual parent of x-fast tries.