Van Emde Boas tree

Function

Let ${\displaystyle {\log }_{2}m=k}$ for some integer ${\displaystyle k}$. Define ${\displaystyle M=2^m}$. A vEB tree T over the universe ${\displaystyle \{0,\dots ,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},\dots ,(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

The operation FindNext(T, x) that searches for the successor of an element x in a vEB tree proceeds as follows: If x<T.min 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 < T.children[i].max, 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 children level needs to be composed with the high bits to form a complete next element.

<b id="mwjw">function</b> FindNext(T, x) <b id="mwkA">if</b> x < T.min <b id="mwkQ">then</b> <b id="mwkg">return</b> T.min <b id="mwkw">if</b> x ≥ T.max <b id="mwlA">then</b> <i id="mwlQ">// no next element</i> <b id="mwlg">return</b> M i = floor(x/<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt100" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwlw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span>) lo = x mod <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt101" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwmA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> <b id="mwmQ">if</b> lo < T.children[i].max <b id="mwmg">then</b> <b id="mwmw">return</b> (<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt102" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwnA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) <b id="mwnQ">return</b> (<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt103" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwng"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> j) + T.children[j].min <b id="mwnw">end</b>

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

Insert

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

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

In code:

<b id="mw5g">function</b> Insert(T, x) <b id="mw5w">if</b> T.min == x || T.max == x <b id="mw6A">then</b> <i id="mw6Q">// x is already inserted</i> <b id="mw6g">return</b> <b id="mw6w">if</b> T.min > T.max <b id="mw7A">then</b> <i id="mw7Q">// T is empty</i> T.min = T.max = x; <b id="mw7g">return</b> <b id="mw7w">if</b> x < T.min <b id="mw8A">then</b> swap(x, T.min) <b id="mw8Q">if</b> x > T.max <b id="mw8g">then</b> T.max = x i = floor(x / <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt163" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mw8w"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span>) lo = x mod <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt164" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mw9A"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> Insert(T.children[i], lo) <b id="mw9Q">if</b> T.children[i].min == T.children[i].max <b id="mw9g">then</b> Insert(T.aux, i) <b id="mw9w">end</b>

The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes 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 ⁠${\displaystyle T(m)=T(m/2)+O(1)}$⁠ as before.

Delete

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

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

In code:

<b id="mwATI">function</b> Delete(T, x) <b id="mwATM">if</b> T.min == T.max == x <b id="mwATQ">then</b> T.min = M T.max = −1 <b id="mwATU">return</b> <b id="mwATY">if</b> x == T.min <b id="mwATc">then</b> hi = T.aux.min * <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt202" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwATg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> j = T.aux.min T.min = x = hi + T.children[j].min i = floor(x / <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt203" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwATk"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span>) lo = x mod <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt204" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwATo"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> Delete(T.children[i], lo) <b id="mwATs">if</b> T.children[i] is empty <b id="mwATw">then</b> Delete(T.aux, i) <b id="mwAT0">if</b> x == T.max <b id="mwAT4">then</b> <b id="mwAT8">if</b> T.aux is empty <b id="mwAUA">then</b> T.max = T.min <b id="mwAUE">else</b> hi = T.aux.max * <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt205" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\sqrt{M}"}}' id="mwAUI"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle {\sqrt {M}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>M</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83bb1f82e3f098fd52448abdd50cca4f66910ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}"/></span> j = T.aux.max T.max = hi + T.children[j].max <b id="mwAUM">end</b>

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 T.children[i] prior to the deletion.

In practice

The assumption that log m is an integer is unnecessary. The operations ${\displaystyle x\sqrt{M}}$ and ${\displaystyle xmod\sqrt{M}}$ can be replaced by taking only higher-order ⌈m/2⌉ and the lower-order ⌊m/2⌋ bits of 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 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 log(m) new trees containing about 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 O(M) = O(2^m), proportional to the size of the key universe. This can be seen as follows. The recurrence is ${\displaystyle S(M)=O(\sqrt{M})+(\sqrt{M}+1)\cdot S(\sqrt{M})}$. One can show that S(M) = O(M) by induction.

Similar structures

The 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. A naive replacement using hash tables achieves O(n log log M) space (or theta(n log n) in some formulations) because elements can be represented across up to O(log log M) nested levels of active hash tables. To achieve true linear O(n) space, a technique called indirection or bucketing is used: elements are partitioned into local buckets of size theta(log log M) or theta(log M) (using a balanced BST or sorted array), and only the representative element (such as the minimum) of each bucket is indexed in the hash-table-based vEB tree. This preserves the O(log log M) query time since searching inside a bucket of size O(log log M) takes O(log(log log M)) time, which is dominated by the vEB lookup.

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 O(n log M) space while y-fast tries use 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 O(log_w n) time for predecessor/successor queries and updates, where w is the word size. Fusion trees use O(n) space and can be made dynamic with hashing or exponential trees.

Lenhof and Smid present a variant of the vEB tree which uses space O(n) and take O(1) expected amortized time for inserting an element, under the restriction that insertions are in increasing order; in other words, the inserted element is always the new maximum. This structure uses dynamic perfect hashing to implement the tree in small space and moreover decrease the size of the tree by a log log M factor by keeping at the leaves buckets of size log log M.

A space-efficient and partially persistent version of vEB trees was presented by Dietz and Raman. This version uses O(n) space, and supports an insert in the current version in O(log log M) amortized and expected time, while a query on any version remains O(log log M).

Implementations

There is a verified implementation in Isabelle (proof assistant). Both functional correctness and time bounds are proved. Efficient imperative Standard ML code can be generated.