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. It performs all operations in O(log m) time (assuming that an ${\displaystyle m}$ bit operation can be performed in constant time), or equivalently in ${\displaystyle O(\log \log M)}$ time, where ${\displaystyle M=2^{m}}$ is the largest element that can be stored in the tree. The parameter ${\displaystyle M}$ 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 an unideal space efficiency of ${\displaystyle O(M)}$. For example, for storing 32-bit integers (i.e., when ${\displaystyle m=32}$), it requires ${\displaystyle M=2^{32}}$ bits of storage. To resolve this, vEB trees can be modified to achieve ${\displaystyle O(n\log M)}$ space, or similar data structures with equivalent asymptotic time efficiency and space efficiency of ${\displaystyle O(n)}$ (where ${\displaystyle n}$ is the number of stored elements) can be used.

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:

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 ${\displaystyle O(1)}$ time, since the minimum and maximum element are stored as attributes in each tree.

Let ${\displaystyle \log _{2}m=k}$ for some integer ${\displaystyle k}$. Define ${\displaystyle M=2^{m}}$. A vEB tree T over the universe ${\displaystyle \{0,\ldots ,M-1\}}$ has a root node that stores an array T.children of length ${\displaystyle {\sqrt {M}}}$. T.children[i] is a pointer to a vEB tree that is responsible for the values ${\displaystyle \{i{\sqrt {M}},\ldots ,(i+1){\sqrt {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 ${\displaystyle x}$ is stored in the subtree T.children[i] where ${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$. The auxiliary tree T.aux keeps track of which children are non-empty, so T.aux contains the value ${\displaystyle j}$ if and only if T.children[j] is non-empty.

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 ${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$. 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.

Note that, in any case, the algorithm performs ${\displaystyle O(1)}$ work and then possibly recurses on a subtree over a universe of size ${\displaystyle M^{1/2}}$ (an ${\displaystyle m/2}$ bit universe). This gives a recurrence for the running time of ${\displaystyle T(m)=T(m/2)+O(1)}$, which resolves to ${\displaystyle O(\log m)=O(\log \log M)}$.