Chapter 8: van Emde Boas Trees

Source files used: Vanemdeboas (Lecture 4 notes); textbook Chapter 20 (van_Emde Boas_Trees) as support. No worked examples are included.

1. Big Picture

A van Emde Boas (vEB) tree stores integer keys from a fixed universe and answers Successor queries exponentially faster than a balanced search tree.

The Recurrences guide asked: where does $\lg\lg u$ come from? This guide builds a data structure whose operations satisfy $T(u)=T(\sqrt{u})+O(1)$.

$$\boxed{\text{Maintain }n\text{ keys in }\{0,\dots,u-1\}\text{ with Insert, Delete, Successor in }O(\lg\lg u).}$$

The lecture builds it in eight steps:

1. bit vector,
2. split the universe into $\sqrt{u}$ clusters,
3. recurse (clusters and summary are vEB structures),
4. store min and max,
5. do not store min recursively,
6. Delete,
7. space: hash tables,
8. space: indirection.

---

2. Core Ideas

2.1 Why It Matters

• If $u=n^{O(1)}$ or $u=n^{\lg^{O(1)}n}$, then $O(\lg\lg u)=O(\lg\lg n)$ per operation.
• Exponentially faster than balanced search trees ($O(\lg n)$).
• Supports Successor and Predecessor, which hashing does not.
• Application: network routing tables, $u=2^{32}$ for IPv4 (range of IP addresses to output port).

---

2.2 Where $O(\lg\lg u)$ Can Arise

• binary search over $\lg u$ elements,
• $T(\lg u)=T\!\left(\frac{\lg u}{2}\right)+O(1)$, equivalently

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

Every vEB operation must make one recursive call on a structure of size $\sqrt{u}$ plus $O(1)$ work.

---

2.3 Clusters and Summary

Split the universe into $\sqrt{u}$ clusters, each of size $\sqrt{u}$.

• $V.\text{cluster}[i]$: a size-$\sqrt{u}$ vEB for cluster $i$, $0\le i<\sqrt{u}$,
• $V.\text{summary}$: a size-$\sqrt{u}$ vEB; $V.\text{summary}$ contains $i$ iff $V.\text{cluster}[i]$ is nonempty.

---

2.4 The Min and Max Trick

Each structure stores $V.\text{min}$ and $V.\text{max}$.

• Successor can test “is the answer inside $x$‘s cluster?” in $O(1)$ by comparing with that cluster’s max, instead of recursing.
• The min is not stored recursively in any cluster. Inserting into an empty structure only sets min (and max), costing $O(1)$. This is what keeps Insert down to one real recursive call.

Textbook detail: when a tree has two or more elements, the min is not in any cluster, but the max is.

---

2.5 Lower Bound

Pătraşcu and Thorup (2007): $\Omega(\lg\lg u)$ for $u=n^{\lg^{O(1)}n}$ with space $O(n\,\text{polylog}\,n)$, even for the static problem (Successor only, no Insert or Delete). So vEB is optimal in that setting.

---

3. Main Governing Equations and Formulas

3.1 Step 1: Bit Vector

$V[x]=1$ iff $x$ is in the set.

• Insert, Delete: $O(1)$,
• Successor, Predecessor: $O(u)$ (scan).

---

3.2 Step 2: high, low, index

If $x=i\sqrt{u}+j$ with $0\le j<\sqrt{u}$, then $V[x]=V.\text{cluster}[i][j]$:

$$\text{high}(x)=\left\lfloor\frac{x}{\sqrt{u}}\right\rfloor=i$$ $$\text{low}(x)=x\bmod\sqrt{u}=j$$ $$\text{index}(i,j)=i\sqrt{u}+j$$

In binary, high and low are the high-order and low-order halves of the bits of $x$. Lecture example: $u=16$, $x=9=1001_2$, so $\text{high}(x)=10_2=2$ and $\text{low}(x)=01_2=1$.

With flat clusters (no recursion): Insert $O(1)$; Successor checks inside the cluster, then finds the next nonempty cluster, then the min in it, each $O(\sqrt{u})$, total $O(\sqrt{u})$.

---

3.3 Step 3: Naive Recursion

Insert updates the cluster and the summary:

$$T(u)=2T(\sqrt{u})+O(1)\;\Rightarrow\;T'(\lg u)=2T'\!\left(\frac{\lg u}{2}\right)+O(1)=O(\lg u)$$

Successor recurses in the cluster, then the summary, then the next cluster:

$$T(u)=3T(\sqrt{u})+O(1)\;\Rightarrow\;O\big((\lg u)^{\lg3}\big)=O(\lg^{1.585}u)$$

Both are too slow. The lecture’s conclusion: reduce to one recursion.

---

3.4 Step 4: Successor with Max

Successor(V, x):
    i = high(x)
    if low(x) < V.cluster[i].max:
        j = Successor(V.cluster[i], low(x))
    else:
        i = Successor(V.summary, high(x))
        j = V.cluster[i].min
    return index(i, j)

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

Exactly one recursive call; reading a min or max is $O(1)$. Maintaining min and max adds $O(1)$ to Insert (if $x<V.\text{min}$ set $V.\text{min}=x$; if $x>V.\text{max}$ set $V.\text{max}=x$).

---

3.5 Step 5: Min Not Stored Recursively

Successor first checks the min specially:

if x < V.min: return V.min

Insert:

Insert(V, x):
    if V.min == None:                       # empty case, O(1)
        V.min = V.max = x; return
    if x < V.min: swap x <-> V.min
    if x > V.max: V.max = x
    if V.cluster[high(x)].min == None:      # cluster was empty
        Insert(V.summary, high(x))
    Insert(V.cluster[high(x)], low(x))

If both recursive calls happen, the second one hits the empty case and costs $O(1)$. So

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

---

3.6 Step 6: Delete

Delete(V, x):
    if x == V.min:                          # find new min
        i = V.summary.min
        if i == None:                       # now empty, O(1)
            V.min = V.max = None; return
        x = V.min = index(i, V.cluster[i].min)   # unstore new min
    Delete(V.cluster[high(x)], low(x))
    if V.cluster[high(x)].min == None:      # cluster now empty
        Delete(V.summary, high(x))          # second call
    if x == V.max:                          # update V.max
        if V.summary.max == None:           # just min now
            V.max = V.min
        else:
            i = V.summary.max
            V.max = index(i, V.cluster[i].max)

If the second call happens, the first call was cheap (it just deleted the only element, a min). So

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

---

3.7 Step 7: Space $O(n\lg\lg u)$

The structure so far uses $\Theta(u)$ space. Improvement:

• only create nonempty clusters; if $V.\text{min}$ becomes None, deallocate $V$,
• store $V.\text{cluster}$ as a hash table of nonempty clusters,
• an Insert may create a new structure (filling a min) $\Theta(\lg\lg u)$ times, and this can really happen,
• charge each pointer and hash-table cell to the structure it points to.

$$\text{space}=O(n\lg\lg u)\quad\text{(randomized, because of hashing)}$$

---

3.8 Step 8: Indirection, Space $O(n)$

• Store small vEB structures with $n=O(\lg\lg u)$ elements as a BST or even an array: $O(\lg\lg n)$ time once in the base case.
• There are $O\!\left(\frac{n}{\lg\lg u}\right)$ such disjoint small structures:

$$O\!\left(\frac{n}{\lg\lg u}\cdot\lg\lg u\right)=O(n)\text{ space for the small ones}$$

• Larger structures store pointers to them: also $O(n)$ space.
• Details: split and merge small structures as they grow and shrink.

---

4. Problem-Solving Workflow

4.1 Analyzing a vEB-Style Operation

1. Count the recursive calls on size-$\sqrt{u}$ structures per operation.
2. Write $T(u)=kT(\sqrt{u})+O(1)$.
3. Substitute $m=\lg u$: $S(m)=kS(m/2)+O(1)$.
4. Solve with the master theorem and convert back:
   • $k=1$: $O(\lg\lg u)$,
   • $k=2$: $O(\lg u)$,
   • $k=3$: $O(\lg^{1.585}u)$.
5. If $k>1$, look for an $O(1)$ test (min, max, empty check) that removes a call, or show one of the calls is $O(1)$.

4.2 Tracing an Operation

1. Compute $\text{high}(x)$ and $\text{low}(x)$.
2. Check the special cases first: empty structure, $x<V.\text{min}$, $x=V.\text{min}$.
3. Decide which single structure to recurse into (cluster or summary).
4. Rebuild the answer with $\text{index}(i,j)$.

---

5. Decision Rules / Decision Trees

5.1 Successor$(V,x)$

$x<V.\text{min}$? → return $V.\text{min}$

$\text{low}(x)<V.\text{cluster}[\text{high}(x)].\text{max}$? → answer is in $x$‘s cluster: recurse on the cluster with $\text{low}(x)$

Otherwise? → recurse on the summary to find the next nonempty cluster $i$ → answer is $\text{index}(i,V.\text{cluster}[i].\text{min})$

5.2 Insert$(V,x)$

$V$ empty? → set $V.\text{min}=V.\text{max}=x$, done in $O(1)$

$x<V.\text{min}$? → swap $x$ and $V.\text{min}$, insert the old min instead

Target cluster was empty? → insert $\text{high}(x)$ into the summary; the cluster insert is then $O(1)$

5.3 Which Space Version?

Simple and $u$ is small? → $\Theta(u)$ arrays

Want $O(n\lg\lg u)$? → hash tables of nonempty clusters (randomized)

Want $O(n)$? → indirection with small $O(\lg\lg u)$-size structures

---

6. Important Tables / Correlations Needed

6.1 The Eight Steps

Step	Idea	Result	Space
1	bit vector	Insert/Delete $O(1)$, Successor $O(u)$	$\Theta(u)$
2	$\sqrt{u}$ clusters + nonempty flags	Insert $O(1)$, Successor $O(\sqrt{u})$	$\Theta(u)$
3	recurse on clusters and summary	Insert $O(\lg u)$, Successor $O(\lg^{1.585}u)$	$\Theta(u)$
4	store min and max	Successor $O(\lg\lg u)$	$\Theta(u)$
5	min not stored recursively	Insert $O(\lg\lg u)$	$\Theta(u)$
6	Delete	Delete $O(\lg\lg u)$	$\Theta(u)$
7	hash tables, nonempty clusters only	same times	$O(n\lg\lg u)$, randomized
8	indirection	same times	$O(n)$

6.2 Recurrences

Calls per operation	Recurrence	Solution
1	$T(\sqrt{u})+O(1)$	$O(\lg\lg u)$
2	$2T(\sqrt{u})+O(1)$	$O(\lg u)$
3	$3T(\sqrt{u})+O(1)$	$O(\lg^{1.585}u)$

6.3 Textbook Notes

• The textbook allows $u$ to be any power of 2 using the upper square root $\sqrt[\uparrow]{u}=2^{\lceil(\lg u)/2\rceil}$ and lower square root $\sqrt[\downarrow]{u}=2^{\lfloor(\lg u)/2\rfloor}$; its base case is $u=2$.
• Minimum and Maximum are $O(1)$ (just read min and max); Member, Successor, Predecessor, Insert, Delete are $O(\lg\lg u)$.
• A plain vEB tree takes $O(u)$ space and $O(u)$ time to create empty, so it is a poor choice for a handful of operations.

---

7. Key Takeaways

• Goal: Insert, Delete, Successor on keys in $\{0,\dots,u-1\}$ in $O(\lg\lg u)$.
• $\lg\lg u$ comes from $T(u)=T(\sqrt{u})+O(1)$: one recursive call on a $\sqrt{u}$-size structure.
• $\text{high}(x)=\lfloor x/\sqrt{u}\rfloor$, $\text{low}(x)=x\bmod\sqrt{u}$, $\text{index}(i,j)=i\sqrt{u}+j$.
• Naive recursion: Insert $2T(\sqrt{u})$ gives $O(\lg u)$; Successor $3T(\sqrt{u})$ gives $O(\lg^{1.585}u)$.
• Storing max lets Successor pick cluster or summary with an $O(1)$ test.
• Not storing min recursively makes inserting into an empty structure $O(1)$, so Insert has one real recursive call.
• In Delete, if the summary call happens, the cluster call was $O(1)$.
• Space: $\Theta(u)$, then $O(n\lg\lg u)$ with hashing, then $O(n)$ with indirection.
• Lower bound (Pătraşcu and Thorup): $\Omega(\lg\lg u)$, even for static Successor.
• Applications: routing tables with $u=2^{32}$.