1998/03/01 by Conrado Martı́nez, Salvador Roura · 87 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Data Management and Algorithms #Machine Learning and Algorithms #Binary search tree #Random binary tree #Optimal binary search tree #Self-balancing binary search tree #Interval tree #Binary tree #Search tree #K-ary tree #Ternary search tree #Tree (set theory) #Mathematics #Binary number #Set (abstract data type) #Computer science #Binary search algorithm #Combinatorics #Algorithm #Search algorithm #Tree structure #Arithmetic
paper · pdf · doi:10.1145/274787.274812
published in Journal of the ACM 45(2), 288-323 (Association for Computing Machinery)
openalex publication_date 1998/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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.