Van Emde Boas Tree Algorithm

A van Emde Boas tree, or vEB tree, is a tree data structure that implements an associative array over m-bit integer keys, supporting search, insertion, deletion and related operations in O(log m) time regardless of how many keys it actually holds. A team led by the Dutch computer scientist Peter van Emde Boas invented it in 1975. Its speed comes at the cost of space: a straightforward implementation needs memory proportional to the size of the whole key universe rather than to the number of keys actually stored, which makes it impractical for large key spaces such as ordinary 32-bit integers unless it is built with hash tables or bucketing techniques that reduce its memory use to be proportional to the number of stored elements instead; because of this tradeoff, related structures such as x-fast tries, y-fast tries and fusion trees are often used in practice when comparable query speed is needed with better space efficiency.