Splay trees are almost dynamically optimal

2026/07/20 by Petr Chmel, Bernhard Haeupler, Richard Hladík +5 · 1 voice · 1 citation
#cs.DS

paper · pdf

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(loglog n ⋅ log²loglog n)=O(loglog n)-competitive.

Cited by

• Pure Pairing Heaps

Discussions

• 2. Splay tree is ~O(loglog n)-competitive, almost proving the central dynamic optimality conjecture that it is O(1)-competitive arxiv.org/abs/2607.18498 [bsky, 3 points, 1 comments]

Related

• In pursuit of the dynamic optimality conjecture
• A Foundation for Proving Splay is Dynamically Optimal
• Splay trees on trees
• Self-adjusting binary search trees
• Theoretical insights and an experimental comparison of tango trees and multi-splay trees