Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees
From MaRDI portal
Publication:2428686
DOI10.1007/s00453-011-9489-2zbMath1241.68055OpenAlexW2103885358MaRDI QIDQ2428686
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9489-2
rotationsdata structuresbinary search treesoff-line lower boundunordered binary treesWilber's theorem
Trees (05C05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Cites Work
- Unnamed Item
- The pairing heap: A new form of self-adjusting heap
- Static optimality and dynamic search-optimality in lists and trees
- Key-independent optimality
- The cost of offline binary search tree algorithms and the complexity of the request sequence
- Self-adjusting binary search trees
- Rotation Distance, Triangulations, and Hyperbolic Geometry
- Lower Bounds for Accessing Binary Search Trees with Rotations