van Emde Boas Tree

Recursive summary + clusters · high/low bit split · O(log log u) path

insert / member / successor: O(log log u) min / max: O(1) space: O(u)
Slow Fast
present scanning recursion path inserting found

Operation

Insert keys, then run Successor to watch the high/low split recurse into exactly one cluster (or the summary) — the O(log log u) path.

Complexity

OperationTimeWhy
min() / max()O(1)stored aside on the node
member(x)O(log log u)one cluster per recursion level
insert(x)O(log log u)one recursive call (min-aside trick)
successor(x)O(log log u)one cluster, or summary + O(1) min read
delete(x)O(log log u)second recursion only on O(1) empty-cluster path
spaceO(u)O(n) with hashed clusters / y-fast trie

Recurrence: T(u) = T(√u) + O(1) = O(log log u). For u = 16: √16 = 4, so log log 16 = 2 levels.

Operation Log