Lower Bounds for Accessing Binary Search Trees with Rotations

DOI10.1137/0218004MaRDI QIDQ3829056zbMATH OpenOpenAlexFDO

Authors Robert Wilber

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218004

zbMATH Keywords

binary search treedata structureslower boundrotation

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Lower bounds on the rotation distance of binary trees
• An efficient upper bound of the rotation distance of binary trees
• New lower bounds on the cost of binary search trees
• On the upper bound on the rotation distance of binary trees
• scientific article; zbMATH DE number 7651167
• Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees
• scientific article; zbMATH DE number 1439421
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• scientific article; zbMATH DE number 4064505
• Reflections on Optimal and Nearly Optimal Binary Search Trees

Cited in

(28)

• Right-arm rotation distance between binary trees
• On the deque conjecture for the splay algorithm
• New lower bounds on the cost of binary search trees
• On the diameter of tree associahedra
• Diameter estimates for graph associahedra
• Arboral satisfaction: recognition and LP approximation
• A study on splay trees
• Better analysis of binary search tree on decomposable sequences
• Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees
• Layered working-set trees
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• A history of distribution-sensitive data structures
• In pursuit of the dynamic optimality conjecture
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Greedy is an almost optimal deque
• scientific article; zbMATH DE number 3909754 (Why is no real title available?)
• scientific article; zbMATH DE number 7527483 (Why is no real title available?)
• Smooth heaps and a dual view of self-adjusting data structures
• Parameterizing the hardness of binary search tree access sequences by inversion counts
• scientific article; zbMATH DE number 7651207 (Why is no real title available?)
• Optimal binary search trees
• Belga B-trees
• Efficient reorganization of binary search trees
• Competitive Online Search Trees on Trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• The group access bounds for binary search trees
• Hardness amplification for dynamic binary search trees
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying

This page was built for publication: Lower Bounds for Accessing Binary Search Trees with Rotations

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