Van Emde Boas tree

A van Emde Boas tree , also known as a vEB tree or van Emde Boas priority queue, is a <a href="/facts/Tree_data_structure/RcXz9noF">tree data structure</a> which implements an <a href="/facts/Associative_array/IFGd2xcP">associative array</a> with m-bit integer keys. It was invented by a team led by Dutch computer scientist <a href="/facts/Peter_van_Emde_Boas/Mzl3CEla">Peter van Emde Boas</a> in 1975. It performs all operations in <a href="/facts/Big-O_notation/weFFjSWg">O</a>(log m) time (assuming that an 
 
 
 
 m
 
 
 {\displaystyle m}
 
 bit operation can be performed in constant time), or equivalently in 
 
 
 
 O
 (
 log
 ⁡
 log
 ⁡
 M
 )
 
 
 {\displaystyle O(\log \log M)}
 
 time, where 
 
 
 
 M
 =
 
 2
 
 m
 
 
 
 
 {\displaystyle M=2^{m}}
 
 is the largest element that can be stored in the tree. The parameter 
 
 
 
 M
 
 
 {\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 
 
 
 
 m
 =
 32
 
 
 {\displaystyle m=32}
 
), it requires 
 
 
 
 M
 =
 
 2
 
 32
 
 
 
 
 {\displaystyle M=2^{32}}
 
 bits of storage. However, similar data structures with equally good time efficiency and space efficiency of 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 (where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of stored elements) exist, and vEB trees can be modified to require only 
 
 
 
 O
 (
 n
 log
 ⁡
 M
 )
 
 
 {\displaystyle O(n\log M)}
 
 space.

Van Emde Boas tree open-in-new

Van Emde Boas tree