Van Emde Boas tree. 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 standard vEB tree has inadequate 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 efficiency of  (where  is the number of stored elements) exist, and vEB trees can be modified to require only  space.

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

 Let  for some integer .  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  is stored in the subtree  where .  The auxiliary tree  keeps track of which children are non-empty, so  contains the value  if and only if  is non-empty.

FindNext

The operation  that searches for the successor of an element x in a vEB tree proceeds as follows: If  then the search is complete, and the answer is .  If  then the next element does not exist, return M. Otherwise, let .  If , then the value being searched for is contained in , so the search proceeds recursively in . Otherwise, we search for the successor of the value i in .  This gives us the index j of the first subtree that contains an element larger than x.  The algorithm then returns . The element found on the children level needs to be composed with the high bits to form a complete next element.

 function FindNext(T, x)
     if x < T.min then
         return T.min
     if x ≥ T.max then // no next element
         return M
     i = floor(x/)
     lo = x mod 
     
     if lo < T.children[i].max then
         return ( i) + FindNext(T.children[i], lo)
     j = FindNext(T.aux, i)
     return ( j) + T.children[j].min
 end

Note that, in any case, the algorithm performs  work and then possibly recurses on a subtree over a universe of size  (an  bit universe). This gives a recurrence for the running time of , which resolves to .

Insert

The call  that inserts a value  into a vEB tree  operates as follows:

 If T is empty then we set  and we are done.
 Otherwise, if  then we insert  into the subtree  responsible for  and then set .  If  was previously empty, then we also insert  into 
 Otherwise, if  then we insert  into the subtree  responsible for  and then set .  If  was previously empty, then we also insert  into 
 Otherwise,  so we insert  into the subtree  responsible for .  If  was previously empty, then we also insert  into .

In code:
 function Insert(T, x)
     if T.min == x || T.max == x then // x is already inserted
         return
     if T.min > T.max then // T is empty
         T.min = T.max = x;
         return
     if x < T.min then
         swap(x, T.min)
     if x > T.max then
         T.max = x
     i = floor(x / )
     lo = x mod 
     Insert(T.children[i], lo)
     if T.children[i].min == T.children[i].max then
         Insert(T.aux, i)
 end

The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes  time.  So, even though the algorithm sometimes makes two recursive calls, this only occurs when the first recursive call was into an empty subtree.  This gives the same running time recurrence of  as before.

Delete

Deletion from vEB trees is the trickiest of the operations. The call  that deletes a value x from a vEB tree T operates as follows:

 If  then x is the only element stored in the tree and we set  and  to indicate that the tree is empty.
 Otherwise, if  then we need to find the second-smallest value y in the vEB tree, delete it from its current location, and set .  The second-smallest value y is , so it can be found in  time.  We delete y from the subtree that contains it.
 If  and  then we delete x from the subtree  that contains x.
 If  then we will need to find the second-largest value y in the vEB tree and set . We start by deleting x as in previous case. Then value y is either  or , so it can be found in  time.
 In any of the above cases, if we delete the last element x or y from any subtree  then we also delete i from .

In code:
 function Delete(T, x)
     if T.min == T.max == x then
         T.min = M
         T.max = −1
         return
     if x == T.min then
         hi = T.aux.min * 
         j = T.aux.min
         T.min = x = hi + T.children[j].min
     i = floor(x / )
     lo = x mod 
     Delete(T.children[i], lo)
     if T.children[i] is empty then
         Delete(T.aux, i)
     if x == T.max then
         if T.aux is empty then
             T.max = T.min
         else
             hi = T.aux.max * 
             j = T.aux.max
             T.max = hi + T.children[j].max
 end

Again, the efficiency of this procedure hinges on the fact that deleting from a vEB tree that contains only one element takes only constant time.  In particular, the second Delete call only executes if x was the only element in  prior to the deletion.

In practice

The assumption that  is an integer is unnecessary.  The operations  and  can be replaced by taking only higher-order  and the lower-order  bits of , respectively.  On any existing machine, this is more efficient than division or remainder computations.

In practical implementations, especially on machines with shift-by-k and find first zero instructions, performance can further be improved by switching to a bit array once  equal to the word size (or a small multiple thereof) is reached. Since all operations on a single word are constant time, this does not affect the asymptotic performance, but it does avoid the majority of the pointer storage and several pointer dereferences, achieving a significant practical savings in time and space with this trick.

An optimization of vEB trees is to discard empty subtrees. This makes vEB trees quite compact when they contain many elements, because no subtrees are created until something needs to be added to them. Initially, each element added creates about  new trees containing about  pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones. In a full tree of  elements, only  space is used. Moreover, unlike a binary search tree, most of this space is being used to store data: even for billions of elements, the pointers in a full vEB tree number in the thousands.

The implementation described above uses pointers and occupies a total space of , proportional to the size of the key universe. This can be seen as follows. The recurrence is .
Resolving that would lead to .
One can, fortunately, also show that  by induction.

Similar structures 

The  space usage of vEB trees is an enormous overhead unless a large fraction of the universe of keys is being stored. This is one reason why vEB trees are not popular in practice. This limitation can be addressed by changing the array used to store children to another data structure. One possibility is to use only a fixed number of bits per level, which results in a trie. Alternatively, each array may be replaced by a hash table, reducing the space to  (where  is the number of elements stored in the data structure) at the expense of making the data structure randomized.

x-fast tries and the more complicated y-fast tries have comparable update and query times to vEB trees and use randomized hash tables to reduce the space used. x-fast tries use  space while y-fast tries use  space.

Fusion trees are another type of tree data structure that implements an associative array on w-bit integers on a finite universe. They use word-level parallelism and bit manipulation techniques to achieve  time for predecessor/successor queries and updates, where  is the word size. Fusion trees use  space and can be made dynamic with hashing or exponential trees.

Implementations 
There is a verified implementation in Isabelle (proof assistant). Both functional correctness and time bounds are proved.
Efficient imperative Standard ML code can be generated.

See also 
 Integer sorting
 Tango tree

References

Further reading

 Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). Lecture 11 notes. March 22, 2012.
 

Computer science articles needing expert attention
Priority queues
Search trees