In Pursuit of the Dynamic Optimality Conjecture

DOI10.1007/978-3-642-40273-9_16zbMath1395.68101arXiv1306.0207OpenAlexW1624114741MaRDI QIDQ2848978

John Iacono

Publication date: 13 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.0207

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Greedy Is an Almost Optimal Deque ⋮ A study on splay trees ⋮ Better analysis of binary search tree on decomposable sequences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Pairing heaps: the forward variant. ⋮ Belga B-trees ⋮ Multi-Finger Binary Search Trees ⋮ Competitive Online Search Trees on Trees

Cites Work

• Unnamed Item
• The power and limitations of static binary search trees with lazy finger
• Static optimality and dynamic search-optimality in lists and trees
• A unified access bound on comparison-based dynamic dictionaries
• De-amortizing Binary Search Trees
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Self-adjusting binary search trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Self-Organizing Binary Search Trees
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• An Explanation of Splaying
• Upper Bounds for Maximally Greedy Binary Search Trees
• Combining Binary Search Trees
• Dynamic Optimality—Almost