Building a van Emde Boas tree for fast predecessor queries

A predecessor query asks which stored integer is closest to, but not greater than, a supplied key. It appears whenever an application must find the last event before a timestamp, the nearest occupied position before a requested index, or the previous price level allowed by a rule. Fast answers matter because these lookups often sit directly on an interaction path.

A van Emde Boas tree, usually written vEB, serves a known universe of integers from zero to a fixed power-of-two bound. It divides keys into high and low parts and maintains a summary of occupied clusters. This supports insertion, deletion, membership, successor and predecessor operations in O(log log U) time, where U is the universe size. The problem-solving practice material on hello ML links these ideas to programming exercises.

A Python implementation for U=256 makes the invariants and query paths concrete. Predecessor(x) returns the greatest key less than or equal to x; successor(x) is strict, returning the smallest key greater than x. The example also shows when a bitmap or ordered tree is more practical.

When predecessor queries become the bottleneck

Predecessor searches become costly when a service repeatedly scans a sorted collection. A departure board may need the last vehicle record before a requested time; an auction engine may need the highest earlier bid below a limit; a scheduler may need the latest interval that does not overlap a booking. Each task needs one boundary answer, not a complete scan.

The structure must balance update and query costs. A balanced binary search tree gives O(log n) for sparse keys and arbitrary insertions, but a van Emde Boas tree exploits dense integer keys to reach O(log log U). Its recursion and fixed universe are worthwhile only when those properties match the workload.

The recursive cluster layout

Choose U as a power of two whose exponent is also a power of two. For U=256, the high and low halves are 16 bits. The root splits x into high(x)=x div 16 and low(x)=x mod 16, then selects one of 16 clusters. Each cluster owns a 16-value universe, which splits into four clusters of four values. A two-value node is the base case, so a lookup makes at most three recursive descents.

Every node stores its smallest and largest keys. A summary bitmask marks occupied child clusters. At the root, a set bit at index 1 means cluster 1 contains a key; inside a cluster, the same rule applies to smaller groups. These summaries let a query jump over empty regions instead of visiting them one by one.

Each node uses its own universe size as an empty sentinel, outside that node’s valid range. A named constant or None would also work. The key invariant is that each cluster’s extrema match the keys beneath it, and every occupied child has its summary bit set.

Managing membership and structural changes

Insertion descends to the cluster selected by the high part. If that child was empty, its summary bit is enabled before the recursive insertion. The node then refreshes its minimum and maximum from the first and last occupied clusters. This implementation treats keys as a set and ignores duplicates.

Deletion follows the same path, then clears the child’s summary bit if the child became empty. Recomputing extrema upwards handles deletion of a minimum, maximum or only member. The base case distinguishes nodes holding zero, one or two keys.

Because summaries belong to nodes rather than individual keys, they stay small relative to the full universe. In the U=256 example, the largest summary has 16 bits. This compactness suits dense bounded domains such as bitmap positions or compact schedule identifiers.

A working Python implementation

The implementation uses Python integers as bitmasks and recursively creates child nodes. It accepts 2, 4, 16, 256 and compatible larger powers, although the examples target 256 values. Writes outside the universe raise an error rather than becoming negative indices.

from math import isqrt


class VEBTree:
    def __init__(self, universe_size=256):
        exponent = universe_size.bit_length() - 1
        valid = (
            universe_size >= 2
            and universe_size == (1 << exponent)
            and (exponent & (exponent - 1)) == 0
        )
        if not valid:
            raise ValueError("Universe must be 2**(2**k)")

        self.u = universe_size
        self.minimum = self.maximum = self.u

        if self.u > 2:
            self.high = isqrt(self.u)
            self.low = self.u // self.high
            self.summary = 0
            self.clusters = [
                VEBTree(self.low) for _ in range(self.high)
            ]

    @property
    def empty(self):
        return self.minimum == self.u

    def _refresh(self):
        if not self.summary:
            self.minimum = self.maximum = self.u
            return

        first = (self.summary & -self.summary).bit_length() - 1
        last = self.summary.bit_length() - 1
        self.minimum = first * self.low + self.clusters[first].minimum
        self.maximum = last * self.low + self.clusters[last].maximum

    def insert(self, x):
        if not 0 <= x < self.u:
            raise ValueError("Key outside universe")

        if self.u == 2:
            if self.empty:
                self.minimum = self.maximum = x
            else:
                self.minimum = min(self.minimum, x)
                self.maximum = max(self.maximum, x)
            return

        high, low = divmod(x, self.low)
        if self.clusters[high].empty:
            self.summary |= 1 << high
        self.clusters[high].insert(low)
        self._refresh()

    def delete(self, x):
        if not 0 <= x < self.u:
            raise ValueError("Key outside universe")

        if self.u == 2:
            if self.empty:
                return
            if x == self.minimum:
                if x == self.maximum:
                    self.minimum = self.maximum = self.u
                else:
                    self.minimum = self.maximum
            elif x == self.maximum:
                self.maximum = self.minimum
            return

        high, low = divmod(x, self.low)
        self.clusters[high].delete(low)
        if self.clusters[high].empty:
            self.summary &= ~(1 << high)
        self._refresh()

    def contains(self, x):
        if not 0 <= x < self.u:
            return False
        if self.u == 2:
            return self.minimum <= x <= self.maximum

        high, low = divmod(x, self.low)
        return self.clusters[high].contains(low)

    def predecessor(self, x):
        if self.empty or x < self.minimum:
            return None
        if x >= self.maximum:
            return self.maximum
        if self.u == 2:
            return self.minimum

        high, low = divmod(x, self.low)
        local = self.clusters[high].predecessor(low)
        if local is not None:
            return high * self.low + local

        lower = self.summary & ((1 << high) - 1)
        if not lower:
            return None

        previous = lower.bit_length() - 1
        return previous * self.low + self.clusters[previous].maximum

    def successor(self, x):
        if self.empty:
            return None
        if x < self.minimum:
            return self.minimum
        if x >= self.maximum:
            return None
        if self.u == 2:
            return self.maximum

        high, low = divmod(x, self.low)
        local = self.clusters[high].successor(low)
        if local is not None:
            return high * self.low + local

        upper = self.summary >> (high + 1)
        if not upper:
            return None

        following = high + (upper & -upper).bit_length()
        return following * self.low + self.clusters[following].minimum

After inserting 4, 19, 23, 71 and 200, a predecessor query for 70 returns 23, while one for 71 returns 71. Deleting 23 changes the answer for 70 to 19. These examples make inclusive and strict boundary behaviour easy to inspect.

Python’s arbitrary-precision integers are convenient, but their operations are not automatically constant-time as a universe grows. For U=256 the masks are tiny; the O(log log U) claim describes the classical recursive layout under its usual machine-model assumptions. Larger domains require profiling of mask operations and object allocation.

Tracing a query through the hierarchy

For x=70, the root computes high(x)=4 and low(x)=6. Cluster 4 contains 71 but nothing at or below local key 6, so its recursive predecessor returns None. The root then finds the highest occupied lower cluster and takes its maximum, 23. It never scans the gap between 23 and 70.

The successor path mirrors this but excludes x. It searches the current cluster above the local key; if that fails, it finds the next occupied cluster and returns its minimum. Shortcuts handle values below the global minimum or above the global maximum, avoiding recursion at common boundaries.

Correctness rests on ordered clusters and accurate extrema. If a suitable key exists in the current cluster, recursion finds it; otherwise only a lower cluster can hold the predecessor. The summary identifies that cluster, whose maximum is the answer. Random differential tests against a sorted list can verify the invariant over long update sequences.

A practical implementation checklist

Before adopting this structure, check that its assumptions match the workload and that its constant factors justify the recursion. A focused checklist separates design choices from validation.

Design choices:

• Confirm that the universe is fixed, bounded and integer-valued.
• Compare against a plain bitmap for very small universes.
• Include mask width and object allocation in profiling.
• Prefer an ordered tree for sparse or unbounded keys.

Performance claims should use the production key distribution. Dense data favours cluster summaries, while sparse data can leave most bits clear and still pay for the hierarchy.

Validation cases:

• Test empty, singleton, exact-match and boundary queries.
• Delete the minimum, maximum and only member in turn.
• Define duplicate handling and verify membership results.
• Differential-test random operations against a sorted list.

Documentation should state whether the universe is fixed, how out-of-range reads behave and whether deletion preserves tombstones. Those semantics matter when several components share an index.

Australian deployment considerations and alternatives

For an Australian deployment, a vEB index might sit behind a live journey planner. Sydney’s Opal, Melbourne’s Myki and Brisbane’s Translink support capped, contactless travel, and many commuters check disruptions on a phone. An index could find the latest vehicle event before a requested timestamp while leaving transport rules outside the data structure.

Australian daylight-saving transitions reinforce storing timestamps in UTC instead of repeating local clock values. When operational feeds are linked to accounts, the Privacy Act 1988 and Australian Privacy Principles make data minimisation, access control and identifier separation important design concerns.

Australian banks, payment providers and superannuation platforms often evaluate threshold rules that fit this model. Reuse still depends on universe density, update frequency and audit requirements. Adaptation questions can be directed through the editorial contact channel at hello ML. The alternatives differ in complexity and constant factors; here, w denotes the machine-word size used by a bit operation.

Structure	Predecessor query	Insert or delete	Space	Strong fit
van Emde Boas tree	O(log log U)	O(log log U)	O(U)	Dense, bounded integer keys
Binary trie	O(log U)	O(log U)	O(U) worst case	Variable-width integer keys
Fenwick tree	O(log U)	O(log U)	O(U)	Prefix counts and rank queries
Balanced search tree	O(log n)	O(log n)	O(n)	Sparse or unbounded keys
Python integer bitmap	O(U/w)	O(U/w)	O(U) bits	Very small fixed universes

At U=256, a query visits at most four nodes and every summary remains a small Python integer mask. That makes the structure particularly clear for teaching and for workloads with a genuinely compact key space.