The Dynamic Optimality Conjecture for Splay Trees

Prove that there is a universal constant C such that, for every access sequence, the cost of the splay-tree algorithm is at most C times the minimum cost of any offline dynamic binary search tree algorithm, up to the standard additive initialization term.

Source: Petr Chmel et al., Splay trees are almost dynamically optimal (2026).

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.