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 [53], who shows that the expected height of a random binary search tree is
The name
was coined by Aragon and Seidel [56] who discussed
s and some of their variants. However, their basic structure was
studied much earlier by Vuillemin [61] 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
,
For example, the code
removes from
all values
greater than
and returns a new
containing all
these values. The
operation should run in
expected time.