◇ van Emde Boas Tree

Start — a hotel with a directory. Picture a giant hotel with rooms numbered 0 up to a million, and you want the next occupied room after yours. Knocking on every door is slow. The trick: group the rooms into floors and keep one small "floor directory" that lists only which floors have anyone at all. Now you skip every empty floor at a glance. That is the whole idea behind a van Emde Boas (vEB) tree.

Build — split every number in two. A vEB tree stores integers from a fixed range called the universe, $\{0,1,\dots,U-1\}$. Each number $x$ is split into a high part naming its cluster (the floor), $\text{high}(x)=\lfloor x/\sqrt{U}\rfloor$, and a low part naming the spot inside that cluster, $\text{low}(x)=x \bmod \sqrt{U}$. Every cluster is itself a smaller vEB tree over a universe of size $\sqrt{U}$, and a "summary" vEB tree remembers which clusters are non-empty — exactly the floor directory.

Why it is so fast. Each level shrinks the universe from $U$ to $\sqrt{U}$, and square-rooting collapses a number astonishingly quickly. Starting from $U=2^{32}$: $2^{16}\to 2^{8}\to 2^{4}\to 2^{2}\to 2^{1}$ — just 5 steps. So a search, an insert, or "find the neighbor" costs about $\log_2\log_2 U$ steps. For $U=2^{32}$ that is $\log_2 32 = 5$, versus 32 for a balanced binary search tree.

Deepen — the recurrence. A single operation recurses into one cluster and may also touch the summary, but at most ONE of the two does more than constant work: if the cluster was empty, inserting into it is $O(1)$ and only the summary recurses; if it was non-empty, the summary is untouched and only the cluster recurses. So one call of size $\sqrt{U}$ remains: $T(U)=T(\sqrt{U})+O(1)$. With $U=2^{2^k}$ and $S(k)=T(2^{2^k})$ this is $S(k)=S(k-1)+O(1)=O(k)=O(\log\log U)$. Storing the minimum separately is what guarantees only one recursion — and it makes MIN and MAX truly $O(1)$. The price is memory: a plain vEB reserves every cluster, $O(U)$ space; a hashed version keeps only non-empty clusters, $O(n)$.

Try this in the sim above. The visualizer steps through a worked trace and its counters are live. (1) Drag the n slider, press ↻ Reset, and watch Comparisons grow roughly as $n(n-1)/2$ as more elements are processed. (2) Set the preset to Sorted, then Reverse, pressing Reset each time — Comparisons stay equal while Operations swing from zero up to the maximum. (3) Choose Random and hit Reset a few times to watch the trace reshuffle while the totals stay in the same range.

Step 1 — Motivation. Comparison-based structures: O(log n) per operation — optimal in comparison model. But for integers in {0,...,U-1}: can exploit bit-level structure. van Emde Boas (1975): O(log log U) per operation. For U=2^32: log log U = log 32 = 5. Essentially constant! Trade-off: O(U) space.

Step 2 — Structure. Universe {0,...,U-1}. Split each element x into high(x) = x/√U (cluster index) and low(x) = x mod √U (position within cluster). Recursively: summary vEB on √U (tracks which clusters are non-empty), √U cluster vEBs each on universe {0,...,√U-1}.

Step 3 — Recurrence T(U) = T(√U) + O(1). An operation recurses into one cluster AND may touch the summary, but at most ONE of the two does more than O(1) work: if the target cluster was empty, inserting into it is O(1) (just set its min=max) and only the summary recurses; if the cluster was non-empty, the summary is untouched and only the cluster recurses. So exactly one recursive call on a universe of size √U remains: T(U) = T(√U) + O(1). Base case T(2) = O(1). Substituting U = 2^(2^k) and letting S(k) = T(2^(2^k)) gives S(k) = S(k-1) + O(1), whose solution is S(k) = O(k). Since k = log log U: T(U) = O(log log U). (The naive proto-vEB that always recurses into BOTH gives S(k) = 2S(k-1) + O(1) = O(2^k) = O(log U) — which is exactly why storing min separately, to kill one recursion, matters.)

Step 4 — Minimum and Maximum O(1). min and max stored directly in each vEB node. Access O(1). min is NOT stored recursively in any cluster — this is the key that gives O(1) MIN. INSERT: if x < min, swap x and current min. The old min gets inserted into its cluster.

Step 5 — Space O(U). Recursion: T_space(U) = (1 + √U) · T_space(√U) + O(1). Unrolling: T_space(U) = O(U). For U=2^32: O(4×10^9) words ~ 16GB. Impractical for large U. Solution: hash-based vEB uses O(n) space with O(log log U) expected.

Step 6 — Applications. Integer priority queues in routing (network packets in {0,...,2^16-1}). Computational geometry (integer coordinates). String algorithms (suffix array construction). VLSI design (integer interval scheduling). When U is small (≤ 2^20) and operations are frequent, vEB beats all comparison structures.