A van Emde Boas tree (), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with -bit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975. It performs all operations in time (assuming that an bit operation can be performed in constant time), or equivalently in time, where is the largest element that can be stored in the tree. The parameter is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has poor space efficiency. For example, for storing 32-bit integers (i.e., when ), it requires bits of storage. However, similar data structures with equally good time efficiency and space exist, where is the number of stored elements. Supported operations A vEB supports the operations of an ordered associative array, which includes the usual associative array operations along with two more order operations, FindNext and FindPrevious: Insert: insert a key/value pair with an -bit key Delete: remove the key/value pair with a given key Lookup: find the value associated with a given key FindNext: find the key/value pair with the smallest key which is greater than a given FindPrevious: find the key/value pair with the largest key which is smaller than a given A vEB tree also supports the operations Minimum and Maximum, which return the minimum and maximum element stored in the tree respectively. These both run in time, since the minimum and maximum element are stored as attributes in each tree. Function For the sake of simplicity, let for some integer k. Define . A vEB tree over the universe } has a root node that stores an array of length . is a pointer to a vEB tree that is responsible for the values }. Additionally, T stores two values and as well as an auxiliary vEB tree . Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in and largest value is stored in . Note that is not stored anywhere else in the vEB tree, while is. If T is empty then we use the convention that and . Any other value x is stored in the subtree where . The auxiliary tree keeps