Skip-Splay: Toward Achieving the Unified Bound in the BST Model
From MaRDI portal
Publication:3183455
DOI10.1007/978-3-642-03367-4_18zbMATH Open1253.68106OpenAlexW1526597670MaRDI QIDQ3183455FDOQ3183455
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
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
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Nonnumerical algorithms (68W05)
Cites Work
- Self-adjusting binary search trees
- A unified access bound on comparison-based dynamic dictionaries
- Alternatives to splay trees with \(O(\log n)\) worst-case access times
- 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
- Lower Bounds for Accessing Binary Search Trees with Rotations
- Dynamic Optimality—Almost
- O(log log n)-competitive dynamic binary search trees
- Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
Cited In (6)
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)
