Randomized search trees

DOI10.1007/BF01940876zbMath0857.68030OpenAlexW2099844038MaRDI QIDQ1923861

Yanyan Li

Publication date: 18 February 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940876

zbMATH Keywords

search trees

Mathematics Subject Classification ID

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

• LEDA
• Hull

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