van Emde Boas Tree

Problem

Let $d \in \mathbb{N}^+$ such that $\log \log d \in \mathbb{N}^+$. We want to design a data structure $V$, that maintains $n$ elements from the finite domain $\mathbb{Z}_d \doteq \{0, \ldots, d - 1 \}$, with the following properties:

It supports insert, successor operations in $O(\log \log d)$ time.

Base Case

If $d = 2$, then the tree consists of a bit array $V$ of size two. Insertion and deletion involves setting the corresponding bit to $1$ and $0$, respectively. Finding successor of an element involving scanning the array. All operations has time complexity $O(1)$.

General Cases

Naive Array

We could maintain a bit array $V$ of size $d$. Insertion and deletion can still be performed in $O(1)$ time. However, successor has time complexity $O(d)$.

Naive Recursion

We can partition the bit array $V$ into $\sqrt{d}$ clusters, denoted $V$.cluster$[0]$, $\ldots$, $V$.cluster$[\sqrt{d} - 1]$.
Each cluster consists of $\sqrt{d}$ consecutive elements, and maintains a summary bit for deciding whether it is empty. The summary bits are grouped into an array $V$.summary.

Now insertion time is still $O(1)$. Deletion and successor can be performed in $O(\sqrt{d})$ time.

van Emde Boas Tree

van Emde Boas Tree (vEB Tree) is an advanced data structure based on the divide-and-conquer strategy.

Definition

Denote the structure over domain $d$ as $\text{vEB}(d)$. It is defined recursively as follows:

Definition $\text{vEB}(d)$:

1. If $d = 2$, then $\text{vEB}(d)$ is just a simple bit array of size $2$.
2. Otherwise, $\text{vEB}(d)$ has the following components:
   • Two elements, max and min, each of size $\log d$ bits.
   • Children trees, $c_0, \ldots, c_{\sqrt{d} - 1}$, each of type $\text{vEB} \left(\sqrt{d}\right)$.
   • Summary tree, $s$, of type $\text{vEB} \left(\sqrt{d}\right)$.

Hence, if $d > 2$, then $\text{vEB}(d)$ contains $\big(1 + \sqrt d\big)\,$ $\text{vEB} \left(\sqrt{d}\right)$ subtrees.

Let $V$ be an instance of $\text{vEB}(d)$. If an element $x \in \mathbb{Z}_{d}$ is stored in $V$, we write $x \in V$. The components of $V$ have the following functionalities.

• $V$.max and $V$.min maintain the maximum and minimum elements in the tree. These two elements will not be stored in the children trees or the summary tree.
• For each $i \in \mathbb{Z}_{\sqrt{d}}$, the child tree $V.c_i$ stores elements $x \in V$ for which 1) $x \notin \{ V.\max, V.\min \}$; 2) $\lfloor x / \sqrt{d} \rfloor = i$.
• The summary tree $V.s$ stores the $i \in \mathbb{Z}_{\sqrt d}$ for which $V.c_i$ is not empty.

Operations

We need the following subroutine.

Procedure exchange$(V, x)$:
If $x < V.\min$ then
$\qquad$ swap$(V.\min , x)$;
Elif $V.\max < x$ then
$\qquad$ swap$(V.\max , x)$;

Next we consider inserting an element $x \in \mathbb{Z}_d$ into and $\text{vEB}(d)$ structure $V$.

If $V$ is empty, then the algorithm sets $V.\max$ and $V.\min$ to $x$.

If $V$ consists of one element (in this case, $V.\max = V.\min$), then $x$ is stored in either $V.\max$ or $V.\min$.

Otherwise, $x$ is swapped with $V.\max$, if $x > V.\max$, or $x$ is swapped with $V.\min$, if $x < V.\min$. Then the algorithm extracts the first and the last $(1 / 2) \cdot \log d$ bits, denoted as $x_h$ and $x_\ell$ respectively, from the binary representation of $x$. The value of $x_\ell$ will be inserted into the child tree $V.c_{x_h}$. If $V.c_{x_h}$ is empty, the algorithm needs to insert $x_h$ into the summary tree $V.s$, indicating that $V.c_{x_h}$ is not empty after inserting $x_\ell$ into it.

Procedure insert$(V, x)$:
If $V$ is empty then
$\qquad$ $V.\min \leftarrow x$; $\,V.\max \leftarrow x$;
If $V$ contains only one element then
$\qquad$ exchange$(V, x)$;
else
$\qquad$ exchange$(V, x)$;
$\qquad$ $\big< x_h, x_\ell \big> \leftarrow \left( \lfloor x / \sqrt{d} \rfloor, x \mod{\sqrt{d}} \right)$
$\qquad$ If $V.c_{x_h}$ is empty then
$\qquad$ $\qquad$ insert$(V.s, x_h)$;
$\qquad$ insert$(V.c_{x_h}, x)$;

To find the successor of $x$ from $V$, the algorithm first checks whether $x \ge V.\max$. If so, it returns null.

Otherwise, it inspects the child tree $V.c_{x_h}$. If it is non-empty, and $x$ is smaller than the largest element in $V.c_{x_h}$, the algorithm returns the successor of $x_\ell$ in $V.c_{x_h}$.

If not, the algorithm try to find the smallest $x_h' > x_h$ such that the child tree $V.c_{x_h'}$ is non-empty subtree. If such $x_h'$ exists, the algorithm returns the smallest element from $V.c_{x_h'}$. Otherwise, $V.\max$ is returned.

Procedure successor$(V, x)$:
If $x \ge V.\max$ then
$\qquad$ return null;
$\big< x_h, x_\ell \big> \leftarrow \left( \lfloor x / \sqrt{d} \rfloor, x \mod{\sqrt{d}} \right)$;
If $V.c_{x_h}$ is empty or $V.c_{x_h}.\max \le x$ then
$\qquad$ $x_h' \leftarrow$ successor$(V.s, x)$;
$\qquad$ If $x_h' \neq$ null then
$\qquad$ $\qquad$ return $V.c_{x_h'}.\min$;
$\qquad$ Else
$\qquad$ $\qquad$ return $V.\max$
else
$\qquad$ return successor$(V.c_{x_h}, x_\ell)$.

Time Analysis

Theorem. Inserting an element $x$ into an $\text{vEB}(d)$ instance $V$ has time complexity $O(\log \log d)$.

Proof. The claim holds trivially if $V$ contains zero or one element. Otherwise, let $T(d)$ be the time complexity for inserting $x$ into $V$. We show that

Solving the recursion gives $T(d) \in O(\log \log d)$.

If $V.c_h$ is non-empty, the only one recursion, i.e., insert$(V.c_{x_h}, x)$, is executed. Therefore, $T(d) \le T(\sqrt{d}) + O(1)$ holds.

If $V.c_h$ is empty, two recursions, i.e., insert$(V.s, x)$, insert$(V.c_{x_h}, x)$, are executed. However, in this case, the second recursion has time complexity $O(1)$. Hence, $T(d) \le T(\sqrt{d}) + O(1)$ still holds.

$\square$

Theorem. Finding the successor of an element $x$ from an $\text{vEB}(d)$ instance $V$ has time complexity $O(\log \log d)$.

Proof. The successor operation of $V$ invokes at most one recursive call, therefore its running time $T(d)$ satisfies $T(d) \le T(\sqrt{d}) + O(1)$, which solves to $T(d) \in O(\log \log d)$.

$\square$

Space Analysis

Theorem. $\text{vEB}(d)$ can be implemented with $O(d)$ space.

Proof. Denote the space usage of $\text{vEB}(d)$ as $S(d)$. Then we have $S(2) = O(1)$. For $d > 2$, a $\text{vEB}(d)$ structure stores

1. Elements $\min$ and $\max$, which takes $\Theta(1)$ words.
2. Pointers to $1 + \sqrt{d}$ subtrees, which takes $\Theta(\sqrt{d})$ words.
3. $1 + \sqrt{d}$ subtrees, each taking space $S(\sqrt{d})$.

Therefore, the total space usage is given by

To solve the recursion, assume that $S(4) = 1$ (by proper scaling). Further, assuming that $S(d) \le d - 2$. Then, we can verity that the recursion holds:

$\square$

Theorem. $\text{vEB}(d)$ can be implemented with $O(n \log \log d)$ space.

Proof. One improvement to the previous approach is to avoid maintaining all $\sqrt{d}$ pointers to the children trees $c_0, \ldots, c_{\sqrt{d}}$, and constructing all of them explicitly.

Instead, we construct a child tree only if it is non-empty, and keep a hash table in the $\text{vEB}(d)$ structure, which stores the pointers to these non-empty children trees.

Inserting an element has time complexity $O(\log \log d)$, therefore it can creates at most $O(\log \log d)$ pointers, as well as subtrees. Since when a subtree is created, it takes space $O(1)$, therefore the total space usage is $O(n \log \log d)$.

This bound is tight. Suppose we want to insert an element $x$ into a $\text{vEB}(d)$ structure. If $c_{x_h}$ is empty, then we invoke the recursion insert$(s, x_h)$ to insert $x_h$ into the summary. However, in this case, we need to crete the subtree for $c_{x_h}$ (which takes $O(1)$ space), insert the pointer for $c_{x_h}$ into the hash table (which also takes $O(1)$ space). This can happen for each recursion, therefore the total space overhead is $O(\log \log d)$ for a single insertion.

$\square$

Reference

[1] T. H. Cormen, Ed., Introduction to algorithms 3rd, 3rd ed. Cambridge, Mass: MIT Press, 2009.