Van Emde Boas tree

This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (May 2021) (Learn how and when to remove this message)

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.^[1] 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 inadequate space efficiency. For example, for storing 32-bit integers (i.e., when ${\displaystyle m=32}$, it requires ${\displaystyle M=2^{32}}$ bits of storage. However, similar data structures with equally good time efficiency and with space efficiency of ${\displaystyle O(n)}$ exist, where ${\displaystyle n}$ is the number of stored elements, and vEB trees can be modified to require only ${\displaystyle O(n\log M)}$ space.