On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
From MaRDI portal
Publication:4507339
DOI10.1137/S009753979732699XzbMath0959.68031OpenAlexW1991146548WikidataQ56066204 ScholiaQ56066204MaRDI QIDQ4507339
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/s009753979732699x
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (26)
On minimum generalized Manhattan connections ⋮ Greedy Is an Almost Optimal Deque ⋮ The Parametric Closure Problem ⋮ Self-Adjusting Binary Search Trees: What Makes Them Tick? ⋮ A unified access bound on comparison-based dynamic dictionaries ⋮ Rank-Sensitive Priority Queues ⋮ Skip-Splay: Toward Achieving the Unified Bound in the BST Model ⋮ On the hierarchy of distribution-sensitive properties for data structures ⋮ Proximate point searching ⋮ A priority queue with the time-finger property ⋮ A study on splay trees ⋮ Better analysis of binary search tree on decomposable sequences ⋮ A Linear Potential Function for Pairing Heaps ⋮ Unnamed Item ⋮ Layered working-set trees ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ Adaptive sorting: an information theoretic perspective ⋮ 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
This page was built for publication: On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
