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.
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.
Controls include a universe size selector, buttons to insert, delete, and search for individual integer keys, buttons to query the successor or predecessor of a chosen key, and a step-through trace view that highlights each cluster and summary lookup visited during the current operation.
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?
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.
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.
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 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?