Suggested Final Project Topics

If You’re Interested in Integer Data Structures, Check Out...

van Emde Boas Trees

The van Emde Boas tree was one of the first data structures to support the same operations as a regular bi-

nary search tree (insertion, deletion, lookup, predecessor, and successor) for integers in sublogarithmic

time. It supports all these operations in time O(log log U), where U is the upper bound on the integers

stored. This is both exponentially faster than a regular BST and matches the time bounds of the later y-

fast trie. However, the strategy that the vEB tree uses is fundamentally different than that of the y-fast

trie, and it’s been adapted for use in later data structures.