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

DOI10.1007/S00453-011-9489-2MaRDI QIDQ2428686zbMATH OpenOpenAlexFDO

Authors 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) Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Rotations and the Generation of Binary Trees
• On the upper bound on the rotation distance of binary trees
• Short notes: Some Properties of the Rotation Lattice of Binary Trees
• An efficient upper bound of the rotation distance of binary trees
• Lower bounds on the rotation distance of binary trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• On rotations in fringe-balanced binary trees
• Rotational tree structures on binary trees and triangulations
• An extended result of Kleitman and Saks concerning binary trees
• scientific article; zbMATH DE number 1161281

Cites work

• scientific article; zbMATH DE number 1617246 (Why is no real title available?)
• Key-independent optimality
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Self-adjusting binary search trees
• Static optimality and dynamic search-optimality in lists and trees
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• The pairing heap: A new form of self-adjusting heap

Cited in

(1)

• Lower Bounds for Accessing Binary Search Trees with Rotations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428686)