Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
From MaRDI portal
Publication:963330
DOI10.1016/j.ipl.2007.10.001zbMath1186.68135OpenAlexW2044155041MaRDI QIDQ963330
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
Related Items
Skip-Splay: Toward Achieving the Unified Bound in the BST Model, A study on splay trees, Unnamed Item, Smooth Heaps and a Dual View of Self-Adjusting Data Structures, Competitive Online Search Trees on Trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The design of dynamic data structures
- Online algorithms. The state of the art
- Self-adjusting multi-way search trees
- Organization and maintenance of large ordered indexes
- Optimum binary search trees
- Path balance heuristic for self-adjusting binary search trees
- O(log log n)-competitive dynamic binary search trees
- Amortized Computational Complexity
- Self-adjusting binary search trees
- Lower Bounds for Accessing Binary Search Trees with Rotations
- Self-Organizing Binary Search Trees
- 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
- Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees
- Generalized Template Splay: A Basic Theory and Calculus
- Self-Adjusting k-ary Search Trees
- An Explanation of Splaying
- Experimental and Efficient Algorithms
