Van Emde Boas tree

Van Emde Boas tree
Type	Non-binary tree
Invented	1975
Invented by	Peter van Emde Boas
Asymptotic complexity in big O notation
Space	$O (M)$
Search	$O (log log M)$
Insert	$O (log log M)$
Delete	$O (log log M)$

A Van Emde Boas tree (or Van Emde Boas priority queue; Dutch pronunciation: [vɑn 'ɛmdə 'boːɑs]), also known as a vEB tree, is a tree data structure which implements an associative array with $m$ -bit integer keys. It performs all operations in $O (log m)$ time, or equivalently in $O (log log M)$ time, where $M = 2 m$ is the maximum number of elements that can be stored in the tree. The $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 vEB tree has good space efficiency when it contains a large number of elements, as discussed below. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.

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 $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 \sqrt M, ..., (i +1) \sqrt M -1$ }. Additionally, T stores two values T.min and T.max as well as an auxiliary vEB tree T.aux.

...
Wikipedia