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

DOI10.1007/978-3-642-03367-4_18MaRDI QIDQ3183455zbMATH OpenOpenAlexFDO

Authors 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) Data structures (68P05) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 140487
• Skip lift: a probabilistic alternative to red-black trees
• Skip lift: a probabilistic alternative to red-black trees
• scientific article; zbMATH DE number 65701
• Skip lists - some results on a recent data structure
• The SkipTrie, low-depth concurrent search without rebalancing
• The splay-list: a distribution-adaptive concurrent skip-list
• The splay-list: a distribution-adaptive concurrent skip-list
• Practical approximation algorithms for zero- and bounded-skew trees
• Practical approximation algorithms for zero- and bounded-skew trees

Cites work

• O(log log n)-competitive dynamic binary search trees
• A unified access bound on comparison-based dynamic dictionaries
• Alternatives to splay trees with \(O(\log n)\) worst-case access times
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• Dynamic Optimality—Almost
• 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
• Self-adjusting binary search trees

Cited in

(6)

• Layered working-set trees
• Multi-Finger Binary Search Trees
• A study on splay trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• In pursuit of the dynamic optimality conjecture
• A history of distribution-sensitive data structures

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

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