Better analysis of binary search tree on decomposable sequences

DOI10.1016/j.tcs.2018.12.021zbMath1423.68125arXiv1604.06997OpenAlexW2963787010WikidataQ128636839 ScholiaQ128636839MaRDI QIDQ2419118

Manoj Gupta, Navin Goyal

Publication date: 29 May 2019

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

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

zbMATH Keywords

data structuresbinary search treedynamic optimality conjecture

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• In Pursuit of the Dynamic Optimality Conjecture
• Self-Adjusting Binary Search Trees: What Makes Them Tick?
• An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times
• O(log log n)-competitive dynamic binary search trees
• Self-adjusting binary search trees
• 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
• Weighted dynamic finger in binary search trees
• Upper Bounds for Maximally Greedy Binary Search Trees
• Dynamic Optimality—Almost