Chain-splay trees, or, how to achieve and prove N-competitiveness by splaying

DOI10.1016/J.IPL.2007.10.001MaRDI QIDQ963330zbMATH OpenOpenAlexFDO

Authors George F. Georgakopoulos

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.10.001

zbMATH Keywords

data structurescompetitive analysissplay trees

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Experimental and Efficient Algorithms
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• scientific article; zbMATH DE number 65701
• Self-adjusting binary search trees
• A new path from Splay to dynamic optimality

Cites work

• scientific article; zbMATH DE number 1305510 (Why is no real title available?)
• scientific article; zbMATH DE number 1953882 (Why is no real title available?)
• scientific article; zbMATH DE number 1979484 (Why is no real title available?)
• scientific article; zbMATH DE number 2119638 (Why is no real title available?)
• O(log log n)-competitive dynamic binary search trees
• Amortized Computational Complexity
• An Explanation of Splaying
• Experimental and Efficient Algorithms
• Generalized Template Splay: A Basic Theory and Calculus
• Lower Bounds for Accessing Binary Search Trees with Rotations
• 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
• Online algorithms. The state of the art
• Optimum binary search trees
• Organization and maintenance of large ordered indexes
• Path balance heuristic for self-adjusting binary search trees
• Self-Adjusting k-ary Search Trees
• Self-Organizing Binary Search Trees
• Self-adjusting binary search trees
• Self-adjusting multi-way search trees
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• The design of dynamic data structures

Cited in

(9)

• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• Competitive Online Search Trees on Trees
• Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
• A study on splay trees
• scientific article; zbMATH DE number 65701 (Why is no real title available?)
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• Smooth heaps and a dual view of self-adjusting data structures

This page was built for publication: Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying

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