Van Emde Boas Search

Van Emde Boas search looks up an integer key in a recursive data structure over a fixed universe of keys.

A van Emde Boas tree stores integers from the universe

where $u$ is usually a power of two. The structure supports membership, successor, predecessor, insertion, and deletion in logarithmic time with respect to the bit width of the universe.

Problem

Given a van Emde Boas tree tree with universe size u and a target key x, decide whether x is stored in the tree.

Return true if present, otherwise false.

Structure

Each node stores:

A key is split into a high part and a low part:

The high part selects a cluster. The low part is searched inside that cluster.

Algorithm

First compare against the stored minimum and maximum. If neither matches, recursively search the cluster selected by the high bits.

veb_member(tree, x):
    if x == tree.min or x == tree.max:
        return true

    if tree.u == 2:
        return false

    h = high(tree, x)
    l = low(tree, x)

    if tree.cluster[h] == null:
        return false

    return veb_member(tree.cluster[h], l)

Example

Suppose the universe size is 16, so each key is split using $\sqrt{16} = 4$.

For key 11:

because

The search checks cluster 2, then searches for low key 3 inside that cluster.

Correctness

The minimum and maximum fields store two possible keys directly. If the target equals either one, the algorithm correctly reports success.

For any other key, the recursive decomposition is exact. The value high(x) identifies the only cluster that can contain x, and low(x) identifies the corresponding key inside that cluster.

If the selected cluster is empty, the target cannot be present. If the cluster exists, recursive membership search decides whether the low part occurs there. By induction over universe size, the algorithm returns true exactly when the target is stored.

Complexity

At each recursive step, the universe size changes from $u$ to $\sqrt{u}$.

The recurrence is:

Solving this gives:

Space usage is large in the direct form:

Sparse implementations reduce practical memory by allocating clusters lazily.

When to Use

Van Emde Boas search is useful for integer keys from a bounded universe when very fast ordered operations are needed.

It is appropriate when:

• keys are integers
• the universe size is known
• successor and predecessor are important
• memory overhead is acceptable or sparse allocation is used

For general comparison keys, balanced search trees are simpler. For large sparse integer universes, x fast tries or y fast tries may be more space efficient.

Implementation

import math

class VEBTree:
    def __init__(self, u):
        self.u = u
        self.min = None
        self.max = None

        if u <= 2:
            self.summary = None
            self.cluster = None
        else:
            size = int(math.isqrt(u))
            self.summary = None
            self.cluster = [None] * size

    def high(self, x):
        size = int(math.isqrt(self.u))
        return x // size

    def low(self, x):
        size = int(math.isqrt(self.u))
        return x % size

def veb_member(tree, x):
    if tree is None:
        return False

    if x == tree.min or x == tree.max:
        return True

    if tree.u == 2:
        return False

    h = tree.high(x)
    l = tree.low(x)

    child = tree.cluster[h]
    if child is None:
        return False

    return veb_member(child, l)

type VEBTree struct {
	U       int
	Min     *int
	Max     *int
	Summary *VEBTree
	Cluster []*VEBTree
}

func vebSqrt(u int) int {
	x := 1
	for x*x < u {
		x++
	}
	return x
}

func (t *VEBTree) High(x int) int {
	size := vebSqrt(t.U)
	return x / size
}

func (t *VEBTree) Low(x int) int {
	size := vebSqrt(t.U)
	return x % size
}

func VEBMember(t *VEBTree, x int) bool {
	if t == nil {
		return false
	}

	if t.Min != nil && x == *t.Min {
		return true
	}

	if t.Max != nil && x == *t.Max {
		return true
	}

	if t.U == 2 {
		return false
	}

	h := t.High(x)
	l := t.Low(x)

	if h < 0 || h >= len(t.Cluster) || t.Cluster[h] == nil {
		return false
	}

	return VEBMember(t.Cluster[h], l)
}