van Emde Boas Tree

O(log log U) operations via recursive sqrt(U) clusters

Universe Size

Elements

Tree Depth

Cluster Size

Insert Element (0-15)

Query Value

Current Elements

Operation Log

Recursive Structure

For U = 16, the tree has sqrt(16) = 4 clusters, each of size 4. The summary tracks which clusters are non-empty. This recursion gives O(log log U) time for all operations.

Why It's Fast

Predecessor/successor only needs to check the current cluster or use the summary to jump to the next non-empty cluster. Each level halves the bit-length, giving log log U depth.