Van Emde Boas High-Low Search
Split an integer query into high and low parts and follow a recursive predecessor-search structure.
Free theory articleSplit an integer query into high and low parts and follow a recursive predecessor-search structure.
Concept & interpretation
The van Emde Boas (vEB) tree is a recursive data structure designed to maintain a set of integers in a bounded universe of size U, supporting search, insertion, and deletion operations in O(log log U) time.
experiment
Follow these steps using the module (https://riano.app/module/van-emde-boas-high-low-search) to observe the tree structure and search operations in action:
- Set the Universe to 16.
- Set the Set fixture to "Sparse".
- Select the Query to be 7.
- Observe the results: Predecessor is 4, Successor is 10. The non-empty root clusters count is 3 (clusters 1, 2, 3), matching our manual trace.
- Change Set fixture to "Empty". Observe that both Minimum and Maximum become None, and Membership says No.