van Emde Boas tree  

Type  Nonbinary tree  
Invented  1975  
Invented by  Peter van Emde Boas  

A van Emde Boas tree (Dutch pronunciation: [vɑn ˈɛmdə ˈboːɑs]), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with mbit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.^{[1]} It performs all operations in O(log m) time (assuming that an m bit operation can be performed in constant time), or equivalently in O(log log M) time, where M = 2^{m} is the largest element that can be stored in the tree. The parameter M is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree datastructures is often measured.
The standard vEB tree has poor space efficiency. For example, for storing 32bit integers (i.e., when m=32), it requires M=2^{32} bits of storage. However, similar data structures with equally good time efficiency and with space efficiency of O(n) exist, where n is the number of stored elements, and vEB trees can be modified to require only O(n log M) space.
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:^{[2]}
A vEB tree also supports the operations Minimum and Maximum, which return the minimum and maximum element stored in the tree respectively.^{[3]} These both run in O(1) time, since the minimum and maximum element are stored as attributes in each tree.
For the sake of simplicity, let log_{2} m = k for some integer k. Define M = 2^{m}. A vEB tree T over the universe {0, ..., M−1} has a root node that stores an array T.children of length √M. T.children[i] is a pointer to a vEB tree that is responsible for the values {i√M, ..., (i+1)√M−1}. Additionally, T stores two values T.min and T.max as well as an auxiliary vEB tree T.aux.
Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in T.min and largest value is stored in T.max. Note that T.min is not stored anywhere else in the vEB tree, while T.max is. If T is empty then we use the convention that T.max=−1 and T.min=M. Any other value x is stored in the subtree T.children[i] where i = ⌊x/√M⌋. The auxiliary tree T.aux keeps track of which children are nonempty, so T.aux contains the value j if and only if T.children[j] is nonempty.
The operation FindNext(T, x) that searches for the successor of an element x in a vEB tree proceeds as follows: If x<T.min then the search is complete, and the answer is T.min. If x≥T.max then the next element does not exist, return M. Otherwise, let i = ⌊x/√M⌋. If x<T.children[i].max then the value being searched for is contained in T.children[i] so the search proceeds recursively in T.children[i]. Otherwise, we search for the successor of the value i in T.aux. This gives us the index j of the first subtree that contains an element larger than x. The algorithm then returns T.children[j].min. 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/√M) lo = x mod √M if lo < T.children[i].max then return (√M i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) return (√M j) + T.children[j].min end
Note that, in any case, the algorithm performs O(1) work and then possibly recurses on a subtree over a universe of size M^{.mwparseroutput .sfrac{whitespace:nowrap}.mwparseroutput .sfrac.tion,.mwparseroutput .sfrac .tion{display:inlineblock;verticalalign:0.5em;fontsize:85%;textalign:center}.mwparseroutput .sfrac .num{display:block;lineheight:1em;margin:0.0em 0.1em;borderbottom:1px solid}.mwparseroutput .sfrac .den{display:block;lineheight:1em;margin:0.1em 0.1em}.mwparseroutput .sronly{border:0;clip:rect(0,0,0,0);height:1px;margin:1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2} (an m/2 bit universe). This gives a recurrence for the running time of , which resolves to O(log m) = O(log log M).
The call insert(T, x) that inserts a value x into a vEB tree T operates as follows:
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 / √M) lo = x mod √M 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 O(1) 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.
Deletion from vEB trees is the trickiest of the operations. The call Delete(T, x) that deletes a value x from a vEB tree T operates as follows:
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 * √M j = T.aux.min T.min = x = hi + T.children[j].min i = floor(x / √M) lo = x mod √M 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 * √M 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 T.children[i] prior to the deletion.
The assumption that log m is an integer is unnecessary. The operations and can be replaced by taking only higherorder ⌈m/2⌉ and the lowerorder ⌊m/2⌋ bits of x, respectively. On any existing machine, this is more efficient than division or remainder computations.
In practical implementations, especially on machines with shiftbyk and find first zero instructions, performance can further be improved by switching to a bit array once m 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 obvious 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 log(m) new trees containing about m/2 pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones. In a full tree of M elements, only O(M) 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 O(M) = O(2^{m}), 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 S(M) = M−2 by induction.^{[4]}
The O(M) 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 O(n log log M) (where n is the number of elements stored in the data structure) at the expense of making the data structure randomized.
xfast tries and the more complicated yfast tries have comparable update and query times to vEB trees and use randomized hash tables to reduce the space used. xfast tries use O(n log M) space while yfast tries use O(n) space.
Fusion trees are another type of tree data structure that implements an associative array on wbit integers on a finite universe. They use wordlevel parallelism and bit manipulation techniques to achieve O(log_{w} n) time for predecessor/successor queries and updates, where w is the word size.^{[5]} Fusion trees use O(n) space and can be made dynamic with hashing or exponential trees.
There is a verified implementation in Isabelle (proof assistant).^{[6]} Both functional correctness and time bounds are proved. Efficient imperative Standard ML code can be generated.