READYInsert, delete, or query elements in the vEB tree (U=16).
x5
=
high(x)1
· 4 +
low(x)1
→ cluster[1], pos 1
Universe (U = 16)
Recursive vEB Structure
Statistics
Universe
16
Elements
0
Root Min
--
Root Max
--
Depth
log log 16 = 2
sqrt(U)
4
Legend
Active / Traversed
Min value
Max value
Summary path
Cluster path
Step Log
No operations yet.
How It Works
A van Emde Boas tree stores integers from a universe U = {0..U-1} and supports insert, delete, successor, predecessor, and member in O(log log U) time.
The key insight: each vEB(U) node splits its universe into sqrt(U) clusters of size sqrt(U). A summary vEB tree tracks which clusters are non-empty.
For element x: high(x) = floor(x/sqrt(U)) selects the cluster, low(x) = x mod sqrt(U) gives the position within it.
Recursion depth is log log U because each level square-roots the universe size: 16 → 4 → 2 (base case).