Self-Adjusting Binary Search Trees: What Makes Them Tick?

DOI10.1007/978-3-662-48350-3_26zbMath1466.68032arXiv1503.03105OpenAlexW1924246083MaRDI QIDQ3452794

László Kozma, Mayank Goswami, Thatchaphol Saranurak, Parinya Chalermsook, Kurt Mehlhorn

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Data structures (68P05)

Related Items (13)

An exact characterization of saturation for permutation matrices ⋮ On minimum generalized Manhattan connections ⋮ Self-Adjusting Binary Search Trees: What Makes Them Tick? ⋮ A study on splay trees ⋮ Better analysis of binary search tree on decomposable sequences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Pairing heaps: the forward variant. ⋮ Belga B-trees ⋮ Finding and counting permutations via CSPs ⋮ Multi-Finger Binary Search Trees ⋮ Competitive Online Search Trees on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Sequential access in splay trees takes linear time
• Path balance heuristic for self-adjusting binary search trees
• Self-Adjusting Binary Search Trees: What Makes Them Tick?
• Self-adjusting binary search trees
• Self-Organizing Binary Search Trees
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Generalized Template Splay: A Basic Theory and Calculus
• An Explanation of Splaying
• Upper Bounds for Maximally Greedy Binary Search Trees

This page was built for publication: Self-Adjusting Binary Search Trees: What Makes Them Tick?