Dynamic optimality of splay trees
For $n \ge 1$, store the keys $1, \dots, n$ in a binary search tree $T$. A request sequence is a finite word $X = (x_1, \dots, x_m)$ in these keys, served in the root-access model: before each request, its key is brought to the root by rotations, at a cost of one per rotation plus one for the access. No keys are inserted or deleted. Splaying brings the requested node $x$ to the root as follows. If its parent is the root, rotate $x$ once. Otherwise let $p$ be its parent and $g$ its grandparent: if $x$ and $p$ are both left children or both right children, rotate $p$ above $g$ and then $x$ above $p$; otherwise rotate $x$ twice. Repeat until $x$ is the root. Let $S(T, X)$ be the total cost of serving $X$ by splaying from $T$, and $\operatorname{OPT}(T, X)$ the least cost of any rotation schedule that serves $X$ from the same initial tree with full knowledge of $X$.
Sleator and Tarjan, who introduced splay trees, proved that splaying takes $O(\log n)$ amortized time per access, and conjectured that splay trees are within a constant factor of any binary search tree algorithm, up to an additive $O(n)$, in the model in which an access costs one plus the depth of the accessed node. Chmel, Haeupler, Hladík, Koucký, Roeyskoe, Rozhoň, Sladký and Tarjan showed that optimal costs in that model and in the root-access model agree up to a factor of $2$, and proved that $S(T, X) = O\bigl((\operatorname{OPT}(T, X) + n) \log\log n \, (\log\log\log n)^2\bigr)$ (2026). Tango trees, a different binary search tree algorithm, are $O(\log\log n)$-competitive (Demaine, Harmon, Iacono and Pătraşcu).
Problem. Are there an absolute constant $C < \infty$ and a function $f : \mathbb{N} \to [0, \infty)$ such that $$S(T, X) \le C \operatorname{OPT}(T, X) + f(n)$$ for every $n$, every initial tree $T$ on $n$ keys and every finite request sequence $X$? The additive term depends only on $n$, and $C$ on nothing.
Source: Sleator and Tarjan (1985), Conjecture 1 (the dynamic optimality conjecture), with an additive O(n); stated with an arbitrary additive term f(n), as in Iacono (2013), and in the root-access cost model by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC
- Keywords
- AIM Open Applied Problems, binary search trees, dynamic optimality, splay trees
References
@article{sleator1985,
author = {Sleator, Daniel Dominic and Tarjan, Robert Endre},
title = {Self-adjusting binary search trees},
journal = {J. ACM},
volume = {32},
number = {3},
year = {1985},
pages = {652--686},
doi = {10.1145/3828.3835},
}
@incollection{iacono2013,
author = {Iacono, John},
title = {In pursuit of the dynamic optimality conjecture},
booktitle = {Space-Efficient Data Structures, Streams, and Algorithms},
series = {Lecture Notes in Comput. Sci.},
volume = {8066},
publisher = {Springer},
address = {Berlin, Heidelberg},
year = {2013},
pages = {236--250},
doi = {10.1007/978-3-642-40273-9_16},
eprint = {1306.0207},
archivePrefix = {arXiv},
}
@misc{chmel2026,
author = {Chmel, Petr and Haeupler, Bernhard and Hlad{\'\i}k, Richard and Kouck{\'y}, Michal and Roeyskoe, Antti and Rozho{\v n}, V{\'a}clav and Sladk{\'y}, Ond{\v r}ej and Tarjan, Robert E.},
title = {Splay trees are almost dynamically optimal},
year = {2026},
eprint = {2607.18498},
archivePrefix = {arXiv},
}
@article{demaine2007,
author = {Demaine, Erik D. and Harmon, Dion and Iacono, John and P{\u a}tra{\c s}cu, Mihai},
title = {Dynamic optimality---almost},
journal = {SIAM J. Comput.},
volume = {37},
number = {1},
year = {2007},
pages = {240--251},
doi = {10.1137/S0097539705447347},
}
@misc{aim-splay-dynamic-optimality,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Dynamic optimality of splay trees}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/305-splay-dynamic-optimality.md},
note = {Entry 305 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00387, "Dynamic optimality of splay trees", clopen.solutions.