Abstract:
|
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. |