Randomized Binary Search Trees

We present randomized algorithms for elementary operations over binary search trees. The insertion of a set of keys in any fixed order into an initially empty tree always produces a random binary search tree. The deletion of any key from a random binary search tree results in a random binary search tree. The random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we are able to support accesses by rank without additional storage requirements or modification of the data structures. The cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all operations have guaranteed expected cost ~$O(log n)$, but now irrespective of any assumption on the input distribution.