Random binary search trees have been studied extensively. Devroye [19] 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 [64], who shows that the expected height of a random binary search tree is

The name `Treap` was coined by Seidel and Aragon [67] who discussed
`Treap`s and some of their variants. However, their basic structure was
studied much earlier by Vuillemin [76] who called them Cartesian
trees.

One possible space-optimization of the `Treap` data structure
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
,

Another `Treap` variant that doesn't store priorities at each node is
the randomized binary search tree
of Martínez and Roura [51].
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:

- With probability , the value is added the usual way, as a leaf, and rotations are then done to bring up to the root of this subtree.
- Otherwise (with probability ), the value is recursively added into one of the two subtrees rooted at or , as appropriate.

Removing a value
from a randomized binary search tree is similar
to the process of removing from a `Treap`. 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.

- With probability , we perform a right rotation at , making the root of the subtree that was formerly rooted at .
- With probability , we perform a left rotation at , making the root of the subtree that was formerly rooted at .

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.

- Show how, if we perform a left or right rotation at , then these two quantities can be updated, in constant time, for all nodes affected by the rotation.
- Explain why the same result is not possible if we try to also store the depth, , of each node .

- Design and implement a
`Treap`implementation in which each node keeps track of the minimum and maximum values in its subtree. - Using this extra information, add a 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 .)
- Extend your implementation into a version of a treap that starts all its operations from the node most recently found by .

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.

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.