Splay trees are almost dynamically optimal

Petr Chmel, Bernhard Haeupler, Richard Hladík +5

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…