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 m-bit integer keys.

It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.

bit operation can be performed in constant time), or equivalently in

The standard vEB tree has inadequate space efficiency.

is the number of stored elements) exist, and vEB trees can be modified to require only

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.

time, since the minimum and maximum element are stored as attributes in each tree.

T.children[i] is a pointer to a vEB tree that is responsible for the values

Additionally, T stores two values T.min and T.max as well as an auxiliary vEB tree T.aux.

The auxiliary tree T.aux keeps track of which children are non-empty, so T.aux contains the value

work and then possibly recurses on a subtree over a universe of size

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: 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.

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 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 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.

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(2m), proportional to the size of the key universe.

[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.

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.

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 O(logw n) time for predecessor/successor queries and updates, where w is the word size.

Efficient imperative Standard ML code can be generated.