On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

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

zbMATH Keywords

binary search treeamortized analysissplay treefinger search tree

Mathematics Subject Classification ID

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