4. Divide & Conquer: van Emde Boas Trees

What this lecture covers

The lecture answers a specific question: can you beat the O(log n) bound of a balanced binary search tree for predecessor and successor queries when the stored elements are integers from a known universe of size U? Professor Demaine builds the van Emde Boas (vEB) data structure from scratch, motivating each design choice with a concrete failure of the previous version, until insert, delete and successor all run in O(log log U) time.

This is the fourth lecture in MIT's Design and Analysis of Algorithms course and the first to apply divide-and-conquer thinking to a data structure rather than an algorithm. After watching, you should be able to explain why clustering a universe into sqrt(U)-sized pieces yields a log log U recurrence, and describe the augmentation tricks (storing min and max, and not recursively storing the min) that remove the extra recursive calls that would otherwise make the structure too slow.

Key ideas

• Predecessor problem: given a set of integers from a universe {0, ..., U-1}, support insert, delete and successor (or predecessor) faster than a comparison-based tree by exploiting that the elements are integers.
• Bit vector: the starting structure, an array of size U with a 1 for each present element; insert and delete are constant time, but successor takes O(U) time in the worst case.
• Clustering: splitting the universe into sqrt(U) clusters of size sqrt(U) each, with a summary vector marking which clusters are non-empty, reduces successor to O(sqrt(U)).
• Recursive vEB structure: each cluster and the summary are themselves recursively represented as smaller vEB structures, which is meant to give the recurrence T(U) = T(sqrt(U)) + O(1).
• High and low: high(x) and low(x) split an integer into its cluster number and its position within the cluster, corresponding to the top and bottom halves of the bits of x.
• Storing min and max: augmenting every structure with its minimum and maximum element lets successor decide with one comparison whether the answer is inside the current cluster or must come from the summary structure, cutting successor down to one recursive call.
• Not recursively storing the minimum: on insert, an empty structure just stores the new item in its min field without recursing, which makes the first insert into a cluster free and keeps insert to one effective recursive call.
• Space: a plain array-based vEB structure uses O(U) space; replacing the cluster array with a hash table brings this down to about O(n log log U), and a further trick (not covered in detail) reaches O(n).

Walkthrough

The predecessor problem and the target bound (0:00)

The lecture opens by defining the problem: store a set of n integers from a universe of size U and support insert, delete and successor. A balanced BST already gives O(log n); the goal is O(log log U), which is an exponential improvement when U is polynomial in n. The lecture motivates this with network routers, where routing tables are searched by IP address and U is small and fixed (2^32 for IPv4), so log log U is tiny in practice.

From a recurrence to a bit vector (5:01)

Working backward from the target running time, the class derives that a recurrence of the form T(U) = T(sqrt(U)) + O(1) solves to log log U, since repeatedly taking a square root of U reaches 1 after log log U steps. The simplest starting structure that could support this kind of division is a bit vector indexed by value, where insert and delete are constant time but successor requires scanning up to O(U) cells.

Clustering the universe (13:10)

The universe is split into sqrt(U) clusters of size sqrt(U), with a summary bit vector recording which clusters are non-empty. Successor now works in three steps: search inside the current cluster, then search the summary for the next non-empty cluster, then find the first set bit there, giving O(sqrt(U)) time. The lecture introduces high(x) and low(x) as the quotient and remainder of dividing x by sqrt(U), corresponding to the high and low halves of x's bits, and index(i, j) to recombine them.

Recursing, and why two recursive calls is not enough (25:42)

Each cluster and the summary become smaller recursive vEB structures of size sqrt(U). A naive recursive insert and successor both make two recursive calls, giving T(U) = 2T(sqrt(U)) + O(1), which only solves to O(log U) — no better than a balanced tree. The lecture works through the recursion tree to show why: the "mass" of log U is conserved rather than reduced when there are two branches.

Fixing successor with min and max (37:59)

Augmenting every structure with its minimum eliminates the recursive call used to find the smallest element of a cluster (replaced by a direct field lookup). Augmenting with the maximum lets successor test, in constant time, whether the answer lies inside the current cluster or must come from the summary — so only one of the two recursive branches is ever taken, giving O(log log U) successor.

Fixing insert by not storing the minimum recursively (50:07)

Insert into an empty structure just sets its min (and max) field and returns, without recursing. Because the minimum is never stored recursively, inserting a new smaller item swaps it into the min field and recursively inserts whatever was previously there. This makes the summary update free whenever a cluster was empty, so insert also collapses to one effective recursive call, reaching O(log log U). A small correction is needed in successor to check V.min directly, since it is no longer represented anywhere else.

Delete, the lower bound and space (1:01:28)

Delete mirrors insert, with special handling for deleting the minimum (which may require pulling up a new minimum from the first non-empty cluster) and the maximum (which may require searching the summary's last non-empty cluster). The lecture states, without proof, that O(log log U) is optimal for this kind of structure in most parameter ranges. It closes on space: the array-based version uses O(U) space, but replacing per-level arrays with hash tables reduces this to about O(n log log U), with a further refinement (stopping the recursion early and using linked lists) reaching O(n).

Before you watch

• Be comfortable with recurrences and the master method, since the lecture repeatedly analyzes recursive structures by their recurrence.
• Know how a balanced binary search tree (such as an AVL tree) supports insert, delete and successor in O(log n), since vEB is presented as an improvement over it.
• Basic bit manipulation (masking and shifting) helps with the high/low decomposition of integers.

Check your understanding

1. Why does a recurrence with two recursive calls, T(U) = 2T(sqrt(U)) + O(1), only solve to O(log U) instead of O(log log U)?
2. How does storing the maximum of each cluster let successor avoid making two recursive calls?
3. Why does not recursively storing the minimum element make the first insert into an empty cluster free?
4. What is the space cost of the plain array-based van Emde Boas structure, and how does switching to hash tables for clusters change it?