A Randomized Data Structure for Ordered Sets.
Jon Louis Bentley, Frank Thomson Leighton, Margaret A. Lepley, Donald F. Stanat, John M. Steele · DSpace@MIT (Massachusetts Institute of Technology) · 1989
In this paper, we consider a simple randomized data structure for representing ordered sets, and give a precise combinatorial analysis of the time required to perform various operations. In addition to a practical data structure, this work provides new and nontrivial proabilistic lower bounds and an instance of a practical problem whose randomized complexity is provably less than its deterministic complexity.