Van Emde Boas tree - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Van Emde Boas tree
9 languages
Deutsch<br>فارسی<br>Français<br>日本語<br>한국어<br>Polski<br>Українська<br>Tiếng Việt<br>中文
Edit links
From Wikipedia, the free encyclopedia
Tree data structure
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 treeTypeNon-binary treeInvented1975Invented byPeter van Emde BoasTime complexity in big O notationOperation<br>Average<br>Worst case Search
log<br>log
{\displaystyle O(\log \log M)}
log<br>log
{\displaystyle O(\log \log M)}
Insert
log<br>log
{\displaystyle O(\log \log M)}
log<br>log
{\displaystyle O(\log \log M)}
Delete
log<br>log
{\displaystyle O(\log \log M)}
log<br>log
{\displaystyle O(\log \log M)}
Space complexitySpace
{\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
log<br>log
{\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
32
{\displaystyle m=32}
), it requires
32
{\displaystyle M=2^{32}}
bits of storage. To resolve this, vEB trees can be modified to achieve
log
{\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.
Supported operations<br>[edit]
A vEB tree supports the operations of an ordered associative array, which includes the usual associative array operations along with two more order operations, FindNext and FindPrevious:[2]
Insert: insert a key/value pair with an m-bit key
Delete: remove the key/value pair with a given key
Lookup: find the value associated with a given key
FindNext: find the key/value pair with the smallest key which is greater than a given k
FindPrevious: find the key/value pair with the largest key which is smaller than a given k
A vEB tree also supports the operations Minimum and Maximum, which return the minimum and maximum element stored in the tree respectively.[3] These both run in
{\displaystyle O(1)}
time, since the minimum and maximum element are stored as attributes in each tree.
Function<br>[edit]
An example van Emde Boas tree with dimension 5 and the root's aux structure after 1, 2, 3, 5, 8 and 10 have been inserted.<br>Let
log
{\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.
FindNext<br>[edit]
The operation FindNext(T, x) that searches for the successor of an element x in a vEB tree proceeds as follows: If x 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 , 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...