O(log log n)-competitive dynamic binary search trees
From MaRDI portal
Publication:3581539
DOI10.1145/1109557.1109600zbMath1192.68206OpenAlexW4256485853MaRDI QIDQ3581539
Jonathan C. Derryberry, Daniel Dominic Sleator, Chengwen Chris Wang
Publication date: 16 August 2010
Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1109557.1109600
Searching and sorting (68P10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items (10)
Skip-Splay: Toward Achieving the Unified Bound in the BST Model ⋮ Better analysis of binary search tree on decomposable sequences ⋮ Demand-aware network designs of bounded degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ Belga B-trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ Competitive Online Search Trees on Trees
This page was built for publication: O(log log n)-competitive dynamic binary search trees