Random binary search trees have been studied extensively. Devroye
[14] gives a proof of Lemma 7.1 and related results. There are
much stronger results in the literature as well. The most impressive
of which is due to Reed [55], who shows that the expected height
of a random binary search tree is
where
is the unique solution on
of the
equation
and
.
Furthermore, the variance of the height is constant.
The name Treap was coined by Aragon and Seidel [58] who discussed
Treaps and some of their variants. However, their basic structure was
studied much earlier by Vuillemin [63] who called them Cartesian
trees.
One space-optimization of the Treap data structure that is sometimes
performed is the elimination of the explicit storage of the priority
in each node. Instead, the priority of a node,
, is computed by
hashing
's address in memory (in 32-bit Java, this is equivalent
to hashing
). Although a number of hash functions will
probably work well for this in practice, for the important parts of the
proof of Lemma 7.1 to remain valid, the hash function should be randomized
and have the min-wise independent property: For any distinct
values
, each of the hash values
should be distinct with high probability and, for each
,
for some constant .
One such class of hash functions that is easy to implement and fairly
fast is tabulation hashing [53].
Exercise 7..1
Prove the assertion that there are
sequences that generate
the tree on the right hand side of Figure
7.1. (Hint: Give a
recursive formula for the number of sequences that generate a complete
binary tree of height
and evaluate this formula for
.)
Exercise 7..2
Design and implement the
method that takes as input an
array,
, containing
distinct values and randomly permutes
.
The method should run in
time and you should prove that each
of the
possible permutations of
is equally probable.
Exercise 7..3
Use both parts of Lemma
7.2 to prove that the expected number
of rotations performed by an
operation (and hence also a
operation) is
.
Exercise 7..4
Design and implement a version of a
Treap that includes a
operation that returns the key with rank
in the
Treap. (Hint:
Have each node,
, keep track of the size of the subtree rooted
at
.)
Exercise 7..5
Design and implement a version of a
Treap that supports the
operation. This operation removes all values from the
Treap that
are greater than
and returns a second
Treap that contains all
the removed values.
For example, the code
removes from
all values
greater than
and returns a new Treap
containing all
these values. The
operation should run in
expected time.
opendatastructures.org