Home▸Algorithms & AI▸Van Emde Boas Tree: Beating Log N With Log Log N

🌳 Van Emde Boas Tree: Blazing-Fast Search on Bounded Integers

Explore the van Emde Boas tree, a recursive data structure that supports insert, delete, and search-neighbor operations on integers from a bounded universe in time proportional to the logarithm of the logarithm of the universe size.

Algorithms & AI3DModerate60 FPS

The simulation demonstrates how a van Emde Boas tree recursively splits its universe into clusters and a summary structure, and visually traces how an insert, a successor query, or a predecessor query travels through this recursive hierarchy, jumping directly to the correct cluster via the summary instead of scanning through empty regions.

🔬 What It Demonstrates

🎮 How to Use

Set the universe size to control how many bits and recursive levels the tree has, then insert a handful of integer keys one at a time and watch the cluster and summary structures populate. Run a successor or predecessor query on a chosen key to see the exact recursive path highlighted, including the moment the summary structure is consulted to skip past empty clusters.

💡 Did You Know?

Did you know that a van Emde Boas tree can find the successor of any key among millions of possible values using only a handful of recursive steps, roughly the logarithm of the logarithm of the universe size, which stays under five or six even for a universe of many billions of integers?

⚙ Under the hood

Explore the van Emde Boas tree, a recursive cluster-and-summary data structure that answers successor and predecessor queries in log log U time.

van-emde-boas-treedata-structuresalgorithmssuccessor-queriespriority-queuescomputer-sciencerecursionasymptotic-analysis

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install