van Emde Boas tree

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:Gudmund Skovbjerg Frandsen: [http://www.daimi.au.dk/~gudmund/dynamicF04/vEB.pdf Dynamic algorithms: Course notes on van Emde Boas trees (PDF)] (University of Aarhus, Department of Computer Science) {{dead link|date=April 2025}}

• Insert: insert a key/value pair with an {{math|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 {{math|k}}
• FindPrevious: find the key/value pair with the largest key which is smaller than a given {{math|k}}

A vEB tree also supports the operations Minimum and Maximum, which return the minimum and maximum element stored in the tree respectively. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. {{ISBN|978-0-262-53305-8}}. Chapter 20: The van Emde Boas tree, pp. 531–560.

These both run in $O(1)$ time, since the minimum and maximum element are stored as attributes in each tree.

Image:VebDiagram.svg Let $\backslash log\_2\; m\; =\; k$ for some integer $k$. Define $M\; =\; 2^m$. A vEB tree {{mono|T}} over the universe $\backslash \{0,\; \backslash ldots,\; M\; -\; 1\backslash \}$ has a root node that stores an array {{mono|T.children}} of length $\backslash sqrt\{M\}$. {{mono|T.children[i]}} is a pointer to a vEB tree that is responsible for the values $\backslash \{i\; \backslash sqrt\{M\},\; \backslash ldots,\; (i\; +\; 1)\; \backslash sqrt\{M\}\; -\; 1\backslash \}$. Additionally, T stores two values {{mono|T.min}} and {{mono|T.max}} as well as an auxiliary vEB tree {{mono|T.aux}}.

Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in {{mono|T.min}} and largest value is stored in {{mono|T.max}}. Note that {{mono|T.min}} is not stored anywhere else in the vEB tree, while {{mono|T.max}} is. If T is empty then we use the convention that {{mono|1=T.max=−1}} and {{mono|1=T.min=M}}. Any other value $x$ is stored in the subtree {{mono|T.children[i]}} where $i\; =\; \backslash lfloor\; x\; /\; \backslash sqrt\{M\}\; \backslash rfloor$. The auxiliary tree {{mono|T.aux}} keeps track of which children are non-empty, so {{mono|T.aux}} contains the value $j$ if and only if {{mono|T.children[j]}} is non-empty.

The operation {{mono|FindNext(T, x)}} that searches for the successor of an element x in a vEB tree proceeds as follows: If {{mono|xi = \lfloor x / \sqrt{M} \rfloor. If {{mono|x < T.children[i].max}}, then the value being searched for is contained in {{mono|T.children[i]}}, so the search proceeds recursively in {{mono|T.children[i]}}. Otherwise, we search for the successor of the value i in {{mono|T.aux}}. This gives us the index j of the first subtree that contains an element larger than x. The algorithm then returns {{mono|T.children[j].min}}. The element found on the children level needs to be composed with the high bits to form a complete next element.

function FindNext(T, x)

if x < T.min then

return T.min

if x ≥ T.max then // no next element

return M

i = floor(x/$\backslash sqrt\{M\}$)

lo = x mod $\backslash sqrt\{M\}$

if lo < T.children[i].max then

return ($\backslash sqrt\{M\}$ i) + FindNext(T.children[i], lo)

j = FindNext(T.aux, i)

return ($\backslash sqrt\{M\}$ j) + T.children[j].min

end

Note that, in any case, the algorithm performs $O(1)$ work and then possibly recurses on a subtree over a universe of size $M^\{1/2\}$ (an $m/2$ bit universe). This gives a recurrence for the running time of $T(m)\; =\; T(m/2)\; +\; O(1)$, which resolves to $O(\backslash log\; m)\; =\; O(\backslash log\; \backslash log\; M)$.

The call {{mono|insert(T, x)}} that inserts a value {{mono|x}} into a vEB tree {{mono|T}} operates as follows:

1. If T is empty then we set {{mono|1=T.min = T.max = x}} and we are done.
2. Otherwise, if {{mono|x<T.min}} then we insert {{mono|T.min}} into the subtree {{mono|i}} responsible for {{mono|T.min}} and then set {{mono|1=T.min = x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}
3. Otherwise, if {{mono|x>T.max}} then we insert {{mono|x}} into the subtree {{mono|i}} responsible for {{mono|x}} and then set {{mono|1=T.max = x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}
4. Otherwise, {{mono|T.min< x < T.max}} so we insert {{mono|x}} into the subtree {{mono|i}} responsible for {{mono|x}}. If {{mono|T.children[i]}} was previously empty, then we also insert {{mono|i}} into {{mono|T.aux}}.

In code:

function Insert(T, x)

if T.min == x || T.max == x then // x is already inserted

return

if T.min > T.max then // T is empty

T.min = T.max = x;

return

if x < T.min then

swap(x, T.min)

if x > T.max then

T.max = x

i = floor(x / $\backslash sqrt\{M\}$)

lo = x mod $\backslash sqrt\{M\}$

Insert(T.children[i], lo)

if T.children[i].min == T.children[i].max then

Insert(T.aux, i)

end

The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes {{math|O(1)}} time. So, even though the algorithm sometimes makes two recursive calls, this only occurs when the first recursive call was into an empty subtree. This gives the same running time recurrence of {{tmath|1=T(m)=T(m/2) + O(1)}} as before.

Deletion from vEB trees is the trickiest of the operations. The call {{mono|Delete(T, x)}} that deletes a value x from a vEB tree T operates as follows:

1. If {{mono|1=T.min = T.max = x}} then x is the only element stored in the tree and we set {{mono|1=T.min = M}} and {{mono|1=T.max = −1}} to indicate that the tree is empty.
2. Otherwise, if {{mono|1=x == T.min}} then we need to find the second-smallest value y in the vEB tree, delete it from its current location, and set {{mono|1=T.min=y}}. The second-smallest value y is {{mono|T.children[T.aux.min].min}}, so it can be found in {{math|O(1)}} time. We delete y from the subtree that contains it.
3. If {{mono|x≠T.min}} and {{mono|x≠T.max}} then we delete x from the subtree {{mono|T.children[i]}} that contains x.
4. If {{mono|1=x == T.max}} then we will need to find the second-largest value y in the vEB tree and set {{mono|1=T.max=y}}. We start by deleting x as in previous case. Then value y is either {{mono|T.min}} or {{mono|T.children[T.aux.max].max}}, so it can be found in {{math|O(1)}} time.
5. In any of the above cases, if we delete the last element x or y from any subtree {{mono|T.children[i]}} then we also delete i from {{mono|T.aux}}.

In code:

function Delete(T, x)

if T.min == T.max == x then

T.min = M

T.max = −1

return

if x == T.min then

hi = T.aux.min * $\backslash sqrt\{M\}$

j = T.aux.min

T.min = x = hi + T.children[j].min

i = floor(x / $\backslash sqrt\{M\}$)

lo = x mod $\backslash sqrt\{M\}$

Delete(T.children[i], lo)

if T.children[i] is empty then

Delete(T.aux, i)

if x == T.max then

if T.aux is empty then

T.max = T.min

else

hi = T.aux.max * $\backslash sqrt\{M\}$

j = T.aux.max

T.max = hi + T.children[j].max

end

Again, the efficiency of this procedure hinges on the fact that deleting from a vEB tree that contains only one element takes only constant time. In particular, the second Delete call only executes if x was the only element in {{mono|T.children[i]}} prior to the deletion.

The assumption that {{math|log m}} is an integer is unnecessary. The operations $x\backslash sqrt\{M\}$ and $x\backslash bmod\backslash sqrt\{M\}$ can be replaced by taking only higher-order {{math|⌈m/2⌉}} and the lower-order {{math|⌊m/2⌋}} bits of {{mvar|x}}, respectively. On any existing machine, this is more efficient than division or remainder computations.

In practical implementations, especially on machines with shift-by-k and find first zero instructions, performance can further be improved by switching to a bit array once {{mvar|m}} equal to the word size (or a small multiple thereof) is reached. Since all operations on a single word are constant time, this does not affect the asymptotic performance, but it does avoid the majority of the pointer storage and several pointer dereferences, achieving a significant practical savings in time and space with this trick.

An optimization of vEB trees is to discard empty subtrees. This makes vEB trees quite compact when they contain many elements, because no subtrees are created until something needs to be added to them. Initially, each element added creates about {{math|log(m)}} new trees containing about {{math|m/2}} pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones.

The implementation described above uses pointers and occupies a total space of {{math|O(M) {{=}} O(2^m)}}, proportional to the size of the key universe. This can be seen as follows. The recurrence is $S(M)\; =\; O(\; \backslash sqrt\{M\})\; +\; (\backslash sqrt\{M\}+1)\; \backslash cdot\; S(\backslash sqrt\{M\})$.

Resolving that would lead to $S(M)\; \backslash in\; (1\; +\; \backslash sqrt\{M\})^\{\backslash log\; \backslash log\; M\}\; +\; \backslash log\; \backslash log\; M\; \backslash cdot\; O(\; \backslash sqrt\{M\}\; )$.

One can, fortunately, also show that {{math|S(M) {{=}} M−2}} by induction.{{cite web|last=Rex|first=A|title=Determining the space complexity of van Emde Boas trees|url=https://mathoverflow.net/q/2245 |access-date=27 May 2011}}

The {{math|O(M)}} space usage of vEB trees is an enormous overhead unless a large fraction of the universe of keys is being stored. This is one reason why vEB trees are not popular in practice. This limitation can be addressed by changing the array used to store children to another data structure. One possibility is to use only a fixed number of bits per level, which results in a trie. Alternatively, each array may be replaced by a hash table, reducing the space to {{math|O(n log log M)}} (where {{mvar|n}} is the number of elements stored in the data structure) at the expense of making the data structure randomized.

x-fast tries and the more complicated y-fast tries have comparable update and query times to vEB trees and use randomized hash tables to reduce the space used. x-fast tries use {{math|O(n log M)}} space while y-fast tries use {{math|O(n)}} space.

Fusion trees are another type of tree data structure that implements an associative array on w-bit integers on a finite universe. They use word-level parallelism and bit manipulation techniques to achieve {{math|O(log_w n)}} time for predecessor/successor queries and updates, where {{math|w}} is the word size.{{Cite web |date=4 April 2019 |title=Fusion Tree |url=https://iq.opengenus.org/fusion-tree/ |access-date=30 August 2023 |website=OpenGenus IQ: Computing Expertise & Legacy |language=en}} Fusion trees use {{math|O(n)}} space and can be made dynamic with hashing or exponential trees.

There is a verified implementation in Isabelle (proof assistant).{{cite web |last1=Ammer |first1=Thomas |last2=Lammich |first2=Peter |title=van Emde Boas Trees |url=https://www.isa-afp.org/entries/Van_Emde_Boas_Trees.html |website=Archive of Formal Proofs |date=23 November 2021 |access-date=26 November 2021}} Both functional correctness and time bounds are proved.

Efficient imperative Standard ML code can be generated.

• Integer sorting
• Tango tree

{{reflist}}

{{refbegin}}

• Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). [http://courses.csail.mit.edu/6.851/spring12/scribe/L11.pdf Lecture 11 notes]. March 22, 2012.
• {{cite journal |author-link1=Peter van Emde Boas |last1=van Emde Boas |first1=P. |last2=Kaas |first2=R. |last3=Zijlstra |first3=E. |year=1976 |title=Design and implementation of an efficient priority queue |journal=Mathematical Systems Theory |volume=10 |pages=99–127 |doi=10.1007/BF01683268}}

{{refend}}

{{CS trees}}

{{Authority control}}

Category:Computer science articles needing expert attention

Category:Priority queues

Category:Search trees