RANDOMIZED BINARY SEARCH-TREES

In this paper, we present randomized algorithms over binary search tre es such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tr ee; (b) the deletion of any key from a random binary search tree resul ts in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storag e requirements or modification of the data structures; and (d) the cos t of any elementary operation, measured as the number of visited nodes , is the same as the expected cost of its standard deterministic count erpart; hence, all search and update operations have guaranteed expect ed cost O(log n), but now irrespective of any assumption on the input distribution.