Randomized binary search trees

DOI10.1145/274787.274812zbMath0904.68074OpenAlexW2037107919WikidataQ55891753 ScholiaQ55891753MaRDI QIDQ3841653

Salvador Roura, Conrado Martínez

Publication date: 20 August 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1998-45/

zbMATH Keywords

randomized algorithmsbinary search trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (14)

Random binary search tree with equal elements ⋮ Fibonacci BSTs: a new balancing method for binary search trees ⋮ Emerging behavior as binary search trees are symmetrically updated. ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ Self‐adjusting trees in practice for large text collections ⋮ STRONGER QUICKHEAPS ⋮ Martingales and large deviations for binary search trees ⋮ Deletions in random binary search trees: a story of errors ⋮ Verified analysis of random binary tree structures ⋮ Randomness Preserving Deletions on Special Binary Search Trees ⋮ Maintaining Ideally Distributed Random Search Trees without Extra Space ⋮ Selection by rank inK-dimensional binary search trees

This page was built for publication: Randomized binary search trees