On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
From MaRDI portal
Publication:4507338
DOI10.1137/S0097539797326988zbMath0959.68030OpenAlexW1972748018WikidataQ56066203 ScholiaQ56066203MaRDI QIDQ4507338
Bud Mishra, Jeanette P. Schmidt, Alan R. Siegel, Richard John Cole
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539797326988
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (23)
Greedy Is an Almost Optimal Deque ⋮ The Parametric Closure Problem ⋮ A unified access bound on comparison-based dynamic dictionaries ⋮ Rank-Sensitive Priority Queues ⋮ Skip-Splay: Toward Achieving the Unified Bound in the BST Model ⋮ Proximate point searching ⋮ A study on splay trees ⋮ Better analysis of binary search tree on decomposable sequences ⋮ Unnamed Item ⋮ Layered working-set trees ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Maximum-weight planar boxes in \(O(n^2)\) time (and better) ⋮ On the deque conjecture for the splay algorithm ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ The cost of offline binary search tree algorithms and the complexity of the request sequence ⋮ The power and limitations of static binary search trees with lazy finger ⋮ Belga B-trees ⋮ Multi-Finger Binary Search Trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ In Pursuit of the Dynamic Optimality Conjecture ⋮ Competitive Online Search Trees on Trees ⋮ Randomized splay trees: Theoretical and experimental results.
This page was built for publication: On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences