Let \log_2 m = k for some integer k. Define M = 2^m. A vEB tree over the universe \{0, \ldots, M - 1\} has a root node that stores an array of length \sqrt{M}. is a pointer to a vEB tree that is responsible for the values \{i \sqrt{M}, \ldots, (i + 1) \sqrt{M} - 1\}. Additionally,
T stores two values and as well as an auxiliary vEB tree . Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in and largest value is stored in . Note that is not stored anywhere else in the vEB tree, while is. If
T is empty then we use the convention that and . Any other value x is stored in the subtree where i = \lfloor x / \sqrt{M} \rfloor. The auxiliary tree keeps track of which children are non-empty, so contains the value j if and only if is non-empty.
FindNext The operation that searches for the successor of an element
x in a vEB tree proceeds as follows: If then the search is complete, and the answer is . If then the next element does not exist, return M. Otherwise, let i = \lfloor x / \sqrt{M} \rfloor. If , then the value being searched for is contained in , so the search proceeds recursively in . Otherwise, we search for the successor of the value
i in . This gives us the index
j of the first subtree that contains an element larger than
x. The algorithm then returns . 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 \sqrt{M}) lo = x mod \sqrt{M}
if lo \sqrt{M} i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i)
return (\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(\log m) = O(\log \log M).
Insert The call that inserts a value into a vEB tree operates as follows: • If
T is empty then we set and we are done. • Otherwise, if then we insert into the subtree responsible for and then set . If was previously empty, then we also insert into • Otherwise, if then we insert into the subtree responsible for and then set . If was previously empty, then we also insert into • Otherwise, so we insert into the subtree responsible for . If was previously empty, then we also insert into . 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.max
then T.max = x i = floor(x / \sqrt{M}) lo = x mod \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 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 as before.
Delete Deletion from vEB trees is the trickiest of the operations. The call that deletes a value
x from a vEB tree T operates as follows: • If then
x is the only element stored in the tree and we set and to indicate that the tree is empty. • Otherwise, if then we need to find the second-smallest value
y in the vEB tree, delete it from its current location, and set . The second-smallest value
y is , so it can be found in time. We delete
y from the subtree that contains it. • If and then we delete x from the subtree that contains
x. • If then we will need to find the second-largest value
y in the vEB tree and set . We start by deleting x as in previous case. Then value
y is either or , so it can be found in time. • In any of the above cases, if we delete the last element
x or
y from any subtree then we also delete
i from . 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 * \sqrt{M} j = T.aux.min T.min = x = hi + T.children[j].min i = floor(x / \sqrt{M}) lo = x mod \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 * \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 prior to the deletion.
In practice The assumption that is an integer is unnecessary. The operations x\sqrt{M} and x\bmod\sqrt{M} can be replaced by taking only higher-order and the lower-order bits of , 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 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 new trees containing about 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 , proportional to the size of the key universe. This can be seen as follows. The recurrence is S(M) = O( \sqrt{M}) + (\sqrt{M}+1) \cdot S(\sqrt{M}) . One can show that by induction. ==Similar structures==