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.68055MaRDI 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
rotations; data structures; binary search trees; off-line lower bound; unordered binary trees; Wilber's theorem
05C05: Trees
68P10: Searching and sorting
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
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