Van Emde Boas Trees
Recall from last week: a van Emde Boas (vEB) tree representing
a universe of size u consists of a summary van Emde Boas tree and
√
an array of u cluster van Emde Boas trees, each representing a
√
universe of size u.
Notation. Let V be a vEB tree with universe size u.
• V.summary is the summary vEB tree
• V.cluster is the array of cluster vEB trees
• V.u is the size of the universe
• V.min holds the smallest entry, not yet inserted in the tree,
and acts as an empty/nonempty flag.
• V.max holds a copy of the largest entry
1/7
Van Emde Boas Trees
The predecessor operation – original version
• To find the predecessor of x, find the predecessor of H(x) in
summary, then find the predecessor of L(x) in the
corresponding cluster.
Again, we have to fix some things. Thoughts:
• If cluster[H(x)] is nonempty and L(x) is at least as large as
the smallest value in cluster[H(x)], then we recursively
look for the predecessor of L(x) in cluster[H(x)].
• If one of the above conditions fails, we need to find the
(strict!) predecessor of H(x) in summary, and the largest
entry in the corresponding cluster.
2/7
Van Emde Boas Trees
QUICK EXERCISE. Give a sketch in pseudocode of the
predecessor() operation, including base cases. Assume you have
√
a function key(i, j) that calculates x = i u+j in O(1) time.
Answer
int predecessor(x)
if (min == null || x < min) return no answer
if (x == min) return min
if (x >= max) return max
if (cluster[H(x)].min != null && cluster[H(x)].min <= L(x))
j = cluster[H(x)].predecessor(L(x))
return key(H(x), j)
else
j = summary.predecessor(H(x)-1)
i = cluster[j].max
return key(i, j)
3/7
Van Emde Boas Trees
The delete operation – original version
• To delete x, delete L(x) from cluster[H(x)]. If the
resulting cluster is empty, delete H(x) from summary.
Exercise to the reader: work out the details of how to rewrite this
algorithm so that it requires no more than one recursive call on a
√
universe of size u.
The tricky cases are if min or max needs to be updated. Remember
that these two keys are treated asymmetrically: V.max is contained
in one of the clusters of V, while V.min is not.
4/7
Van Emde Boas Trees
Space required
√
A vEB tree with universe size u comprises u+1 vEB trees with
√ √
universe size u, together with an array of length u and O(1)
additional fields.
Consequently, if S(u) denotes the space required to store a vEB
tree with universe size u, then S(u) satisfies the recurrence relation
√ √ √
(cid:26) (cid:0) (cid:1)
u+1 S( u)+Θ( u), u > 2
S(u) =
O(1), u ≤ 2
Proposition. S(u) ∈ Θ(u).
Proof. Assignment 2.
5/7
Van Emde Boas Trees
The space requirements can be reduced using techniques similar to
those we saw on y-fast tries.
• Replace the cluster array with a hash table. Assume the size
of the hash table is proportional to the number of entries it
contains.
• Don’t instantiate a cluster vEB tree until it becomes
nonempty, and deallocate it if it ever becomes empty.
Exercise to the reader: an empty vEB tree of any universe size
requires O(1) memory. Describe a scenario in which one call to
insert results in the worst-case amount of new memory being
allocated. Conclude that the above changes reduce the required
memory space to O(nloglog(u)).
6/7
Van Emde Boas Trees
Summary to date
• van Emde Boas trees achieve O(loglog(u)) time complexity
on all operations of interest.
This is an improvement over y-fast tries, which had a
worst-case O(log(u)) time for the delete operation.
• However, van Emde Boas trees require ω(n) memory, whereas
we were able to attain a Θ(n) bound with y-fast tries.
This trade-off between space and time occurs frequently.
• The O(loglog(u)) bound is only an improvement on the
standard O(log(n)) performance of balanced search trees if
n > log(u). Neither of these structures makes sense for small
dictionaries.
7/7
