Van Emde Boas tree

van Emde Boas tree
Type	Non-binary tree
Invented	1975
Invented by	Peter van Emde Boas
Time complexity in big O notation Operation Average Worst case Search ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ Insert ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ Delete ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ Space complexity Space ${\displaystyle O(M)}$ ${\displaystyle O(M)}$

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.