Dynamic Optimality—Almost

DOI10.1137/S0097539705447347zbMath1142.68025OpenAlexW2017619076WikidataQ56060743 ScholiaQ56060743MaRDI QIDQ5454250

Erik D. Demaine, Mihai Pǎtraşcu, John Iacono, Dion Harmon

Publication date: 28 March 2008

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

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

zbMATH Keywords

binary search treescompetitivenesssplay trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

On minimum generalized Manhattan connections ⋮ 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 ⋮ Demand-aware network designs of bounded degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ ASA-graphs for efficient data representation and processing ⋮ Belga B-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