Splay trees are almost dynamically optimal

Abstract

Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline dynamic binary search tree. Despite four decades of work, no $o(\log n)$ competitive ratio was known. We prove that splay trees are $O(\log \log n\cdot {\log }^2\log \log n)=\tilde{O}(\log \log n)$-competitive.