In this paper we present randomized algorithms over binary search
trees 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 tree; b) the deletion of any key from a random binary search
tree results 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 storage requirements...
In this paper we present randomized algorithms over binary search
trees 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 tree; b) the deletion of any key from a random binary search
tree results 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 storage requirements or modification of the data
structures; and d) 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 search and update
operations have guaranteed expected cost O(log n), but
now irrespective of any assumption on the input distribution.
Citation
Martinez, C., Roura, S. "Randomized binary search trees". 1997.