Randomized search trees
From MaRDI portal
Publication:1923861
DOI10.1007/BF01940876zbMath0857.68030OpenAlexW2099844038MaRDI QIDQ1923861
Publication date: 18 February 1997
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01940876
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (38)
Distribution of distances in random binary search trees. ⋮ Reductions in binary search trees ⋮ A constant update time finger search tree ⋮ Smoothed analysis of binary search trees ⋮ Rank-Sensitive Priority Queues ⋮ Kinetic and dynamic data structures for convex hulls and upper envelopes ⋮ Straight-line programs: a practical test (extended abstract) ⋮ Random binary search tree with equal elements ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ A mathematical assessment of the isolation random forest method for anomaly detection in big data ⋮ A kinetic triangulation scheme for moving points in the plane ⋮ Improved bounds for finger search on a RAM ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ The analysis of range quickselect and related problems ⋮ Towards a real time algorithm for parameterized longest common prefix computation ⋮ Building Cartesian trees from free trees with \(k\) leaves ⋮ Skip trees, an alternative data structure to skip lists in a concurrent approach ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ An introduction to randomized algorithms ⋮ Markov incremental constructions ⋮ Dynamic Trees with Almost-Optimal Access Cost ⋮ Self‐adjusting trees in practice for large text collections ⋮ Average search and update costs in skip lists ⋮ The CB tree: a practical concurrent self-adjusting search tree ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Deletions in random binary search trees: a story of errors ⋮ Unnamed Item ⋮ The power and limitations of static binary search trees with lazy finger ⋮ Verified analysis of random binary tree structures ⋮ Multi-Finger Binary Search Trees ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Randomness Preserving Deletions on Special Binary Search Trees ⋮ Maintaining Ideally Distributed Random Search Trees without Extra Space ⋮ Kinetic hanger ⋮ Finger search in grammar-compressed strings ⋮ A History of Distribution-Sensitive Data Structures
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Four results on randomized incremental constructions
- A guided tour of Chernoff bounds
- Organization and maintenance of large ordered indexes
- Priority Search Trees
- Biased Search Trees
- Self-adjusting binary search trees
- A unifying look at data structures
- A note on the height of binary search trees
- Fast Multiple-Precision Evaluation of Elementary Functions
- Sorting jordan sequences in linear time using level-linked search trees
- Binary Search Trees of Bounded Balance
This page was built for publication: Randomized search trees
