Van Emde Boas High-Low Search

worked-example

Let us manually trace finding the strict predecessor of 7 in a vEB tree of Universe 16 containing the sparse keys: 1, 4, 7, 10, 15. The universe U=16 splits into clusters of size √16 = 4.

1. The minimum of the root is 1. The remaining keys (4, 7, 10, 15) are distributed across clusters.
2. For key 4: high = 4/4 = 1, low = 4%4 = 0. It is in cluster 1.
3. For key 7: high = 7/4 = 1, low = 7%4 = 3. It is in cluster 1.
4. For key 10: high = 10/4 = 2, low = 10%4 = 2. It is in cluster 2.
5. For key 15: high = 15/4 = 3, low = 15%4 = 3. It is in cluster 3.
6. The summary contains the indices of non-empty clusters: 1, 2, 3.
7. Querying for predecessor of 7: query is 7. High = 1, Low = 3.
8. In cluster 1, minimum is 0, maximum is 3. Since our query's low part is 3, which is greater than the cluster's minimum (0), the predecessor must lie within cluster 1.
9. The predecessor of 3 within cluster 1 (which holds 0 and 3) is 0.
10. Recombining: high * √U + offset = 1 * 4 + 0 = 4.
11. Thus, the strict predecessor of 7 is 4.

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:

1. Set the Universe to 16.
2. Set the Set fixture to "Sparse".
3. Select the Query to be 7.
4. 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.
5. Change Set fixture to "Empty". Observe that both Minimum and Maximum become None, and Membership says No.

limitations

The implementation relies on fixed small universe sizes (4 and 16) to visualize the recursive splits without overwhelming the UI. It assumes a fixed integer domain. The time complexity of O(log log U) requires O(U) space in a direct implementation (as shown here), though hash tables can reduce this space to O(n) in a real-world scenario. The implementation drops any queries outside the range [0, U-1].

references

The recursive bounds rely on the structure properties discussed in formal computer science literature.

• Advanced Data Structures (MIT 6.851): Details the recursive structure and invariants of the van Emde Boas tree, specifically how the minimum is stored outside the clusters to achieve the optimal time bound.