A study on splay trees

DOI10.1016/J.TCS.2018.12.020MaRDI QIDQ2419117zbMATH OpenOpenAlexWikidataFDO

Authors Luís M. S. Russo

Publication date 29 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03148

zbMATH Keywords

amortized analysisbinary search treescompetitive analysisdata structuresdynamic optimalitysplay trees

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality.

Recommendations

• In pursuit of the dynamic optimality conjecture
• A new path from Splay to dynamic optimality
• scientific article; zbMATH DE number 5237331
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Sequential access in splay trees takes linear time

Cites work

• A new path from Splay to dynamic optimality
• A study on splay trees
• A unified access bound on comparison-based dynamic dictionaries
• Amortized Computational Complexity
• An Explanation of Splaying
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• Combining binary search trees
• Dynamic Optimality—Almost
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• scientific article; zbMATH DE number 5764839 (Why is no real title available?)
• scientific article; zbMATH DE number 65701 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• In pursuit of the dynamic optimality conjecture
• Key-independent optimality
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Nearly optimal binary search trees
• On the deque conjecture for the splay algorithm
• 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
• On the sequential access theorem and deque conjecture for splay trees
• Self-adjusting binary search trees
• Self-adjusting binary search trees: what makes them tick?
• Sequential access in splay trees takes linear time
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Static optimality and dynamic search-optimality in lists and trees
• The geometry of binary search trees
• Upper bounds for maximally greedy binary search trees

Cited in

(12)

• Sequential access in splay trees takes linear time
• Key-independent optimality
• Splaying preorders and postorders
• A study on splay trees
• Alternatives to splay trees with O( n) worst-case access times
• In pursuit of the dynamic optimality conjecture
• scientific article; zbMATH DE number 1305510 (Why is no real title available?)
• scientific article; zbMATH DE number 2050892 (Why is no real title available?)
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• A new path from Splay to dynamic optimality
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)

This page was built for publication: A study on splay trees

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