Skip-Splay: Toward Achieving the Unified Bound in the BST Model

DOI10.1007/978-3-642-03367-4_18zbMath1253.68106OpenAlexW1526597670MaRDI QIDQ3183455

Jonathan C. Derryberry, Daniel Dominic Sleator

Publication date: 20 October 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items (6)

A study on splay trees ⋮ Layered working-set trees ⋮ Unnamed Item ⋮ Multi-Finger Binary Search Trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ In Pursuit of the Dynamic Optimality Conjecture

Cites Work

• Unnamed Item
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• A unified access bound on comparison-based dynamic dictionaries
• O(log log n)-competitive dynamic binary search trees
• Self-adjusting binary search trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• 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
• Dynamic Optimality—Almost

This page was built for publication: Skip-Splay: Toward Achieving the Unified Bound in the BST Model