Lower Bounds for Accessing Binary Search Trees with Rotations
From MaRDI portal
Publication:3829056
DOI10.1137/0218004zbMath0674.68014OpenAlexW2016857845MaRDI QIDQ3829056
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
Searching and sorting (68P10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05)
Related Items (23)
Greedy Is an Almost Optimal Deque ⋮ Skip-Splay: Toward Achieving the Unified Bound in the BST Model ⋮ Arboral satisfaction: recognition and LP approximation ⋮ A study on splay trees ⋮ Better analysis of binary search tree on decomposable sequences ⋮ Unnamed Item ⋮ Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees ⋮ Layered working-set trees ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ On the deque conjecture for the splay algorithm ⋮ On the diameter of tree associahedra ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ The cost of offline binary search tree algorithms and the complexity of the request sequence ⋮ Unnamed Item ⋮ Optimal binary search trees ⋮ The power and limitations of static binary search trees with lazy finger ⋮ Belga B-trees ⋮ Right-arm rotation distance between binary trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ In Pursuit of the Dynamic Optimality Conjecture ⋮ Diameter estimates for graph associahedra ⋮ Competitive Online Search Trees on Trees
This page was built for publication: Lower Bounds for Accessing Binary Search Trees with Rotations
