Next: 8. Scapegoat Trees Up: 7. Random Binary Search Previous: 7.2 : A Randomized Contents
Random binary search trees have been studied extensively. Devroye [16] 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 [57], who shows that the expected height of a random binary search tree is
is the unique solution on
of the
equation
and
.
Furthermore, the variance of the height is constant.
The name
was coined by Aragon and Seidel [60] who discussed
s and some of their variants. However, their basic structure was
studied much earlier by Vuillemin [67] who called them Cartesian
trees.
One space-optimization of the
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. 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
,
.
One such class of hash functions that is easy to implement and fairly
fast is tabulation hashing (Section 5.2.3).
Another
variant that doesn't store priorities at each node is
the randomized binarysearch tree of Martínez and Roura [46].
In this variant, every node,
, stores the size,
, of the
subtree rooted at
. Both the
and
algorithms are
randomized. The algorithm for adding
to the subtree rooted at
does the following:
,
is added the usual way,
as a leaf, and rotations are then done to bring
up to the root
of this subtree.
is recursively added into one of the two
subtrees rooted at
or
, as appropriate.
operation in a
where
's node receives a random priority that is smaller than any of the
priorities in
's subtree, and this case occurs with exactly
the same probability.
Removing a value
from a randomized binary search tree is similar
to the process of removing from a
. We find the node,
,
that contains
and then perform rotations that repeatedly increase
the depth of
until it becomes a leaf, at which point we can splice
it from the tree. The choice of whether to perform a left or right
rotation at each step is randomized.
, we perform a right
rotation at
, making
the root of the subtree that was
formerly rooted at
.
, we perform a left
rotation at
, making
the root of the subtree that was
formerly rooted at
.
will perform a left or right
rotation of
.
Randomized binary search trees have the disadvantage, compared to treaps,
that when adding and removing elements they make many random choices and
they must maintain the sizes of subtrees. One advantage of randomized
binary search trees over treaps is that subtree sizes can serve another
useful purpose, namely to provide access by rank in
expected
time (see Exercise 7.10). In comparison, the random priorities
stored in treap nodes have no use other than keeping the treap balanced.
in Figure 7.5.
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 
.)
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.
operation (and hence also a
operation) is 
.
implementation given here so that it does not
explicitly store priorities. Instead, it should simulate them by
hashing the
of each node.
, the height,
, of the subtree rooted at
, and the size,
of
the subtree rooted at
.
, then these two quantities can be updated, in
constant time, for all nodes affected by the rotation.
, of each node
.
from a
sorted array,
, of
elements. This method should run in
worst-case time and should construct a
that is indistinguishable
from one in which the elements of
were added one at a time using
the
method.
given a pointer that is close to the node we are searching for.
implementation in which each
node keeps track of the minimum and maximum values in its subtree.
method
that executes the
operation with the help of a pointer
to the node
(which is hopefully not far from the node that
contains
). This operation should start at
and walk upwards
until it reaches a node
such that
.
From that point onwards, it should perform a standard search
for
starting from
. (One can show that
takes
time, where 
is the number of elements in
the treap whose value is between
and
.)
operations from the node most recently
found by
.
that includes a
operation that returns the key with rank
in the
. (Hint:
Have each node,
, keep track of the size of the subtree rooted
at
.)
, an implementation of the
interface
as a treap. Each node in the treap should store a list item, and an
in-order traversal of the treap finds the items in the same order that
they occur in the list. All the
operations
,
,
and
should run in
expected time.
that supports the
operation. This operation removes all values from the
that
are greater than
and returns a second
that contains all
the removed values.
Example: the code
removes from
all values
greater than
and returns a new
containing all
these values. The
operation should run in
expected time.
Warning: For this modification to work properly and still allow the
method to run in constant time, it is necessary to implement
the modifications in Exercise 7.10.
that supports the
operation, which can be thought of as the inverse of
the
operation. This operation removes all values from the
and adds them to the receiver. This operation presupposes
that the smallest value in
is greater than the largest value in
the receiver. The
operation should run in
expected time.
implementation.