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 [62], who shows that the expected height of a random binary search tree is

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

One possible space-optimization of the 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. 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 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 . 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 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 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.