van Emde Boas Trees

Recursive √u split → O(log log u)

1:00

How a recursive square-root split of the integer universe gives O(log log u) time for all dictionary operations including successor and predecessor.

By the end, you can

Compute high(x), low(x), and index(i, j) for any key in a given universe size.
Describe the recursive structure: √u clusters plus a summary, each a smaller vEB tree.
Explain the lazy-min trick and why it is the reason inserts into empty subtrees are O(1).
Trace the successor algorithm on a small example, identifying which branch fires and why.
Derive that T(u) = T(√u) + O(1) solves to O(log log u) by counting squarerooting steps.
State the Theta(u) space drawback and name the two standard fixes.
Identify when vEB beats a balanced BST and why it cannot store arbitrary comparison keys.

Up next in Advanced Data Structures