# Van Emde Boas Search

# 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

$$
{0, 1, \ldots, u - 1}
$$

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:

| field     | meaning                              |
| --------- | ------------------------------------ |
| `u`       | universe size                        |
| `min`     | smallest stored key                  |
| `max`     | largest stored key                   |
| `summary` | records which clusters are nonempty  |
| `cluster` | recursively stores low parts of keys |

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

$$
x = high(x) \cdot \sqrt{u} + low(x)
$$

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.

```text id="veb0q4"
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`:

$$
high(11) = 2
$$

$$
low(11) = 3
$$

because

$$
11 = 2 \cdot 4 + 3
$$

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

| key | high | low | cluster searched |
| --- | ---: | --: | ---------------: |
| 11  |    2 |   3 |                2 |

## 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:

$$
T(u) = T(\sqrt{u}) + O(1)
$$

Solving this gives:

$$
T(u) = O(\log \log u)
$$

| operation         | time             |
| ----------------- | ---------------- |
| membership search | $O(\log \log u)$ |
| successor         | $O(\log \log u)$ |
| predecessor       | $O(\log \log u)$ |

Space usage is large in the direct form:

$$
O(u)
$$

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

```python id="veb1r8"
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)
```

```go id="veb2s9"
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)
}
```