Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees

DOI10.1007/s00453-011-9489-2zbMath1241.68055OpenAlexW2103885358MaRDI QIDQ2428686

Michael L. Fredman

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

zbMATH Keywords

rotationsdata structuresbinary search treesoff-line lower boundunordered binary treesWilber's theorem

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• 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
• Unnamed Item

This page was built for publication: Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees