Dynamic optimality conjecture
Do splay trees perform as well as any other binary search tree algorithm, up to a constant factor, on every sequence of accesses?
Summary
Why it is open
A binary search tree stores keys in nodes, with smaller keys in each node's left subtree and larger keys in its right subtree. A lookup follows a path from the root, and the tree can be reshaped by rotations, local changes that also cost a step each [3]. A balanced tree answers any lookup among n keys in O(log n) steps, but many sequences of lookups can be served faster [3, 10]. Sleator and Tarjan's splay tree moves each accessed key to the root by a series of rotations, called splaying [1]. They conjectured that for every sequence of lookups the total time of splaying "is no more than O(n) plus a constant times the time required by algorithm A", where A is any algorithm that may rotate anywhere between lookups, even one tailored to the exact sequence [1].
A tree that achieves this, within a constant factor of the optimum on every sequence, is called dynamically optimal [3]. The problem therefore contains two questions: whether splay trees are dynamically optimal, and whether any online tree is. Erik Demaine, Dion Harmon, John Iacono and Mihai Pătraşcu wrote in 2004 that it was not known whether such a data structure exists [3]. Even offline, with the whole sequence known, Demaine and colleagues listed computing or approximating the best cost in polynomial time as an open problem in 2009 [4].
For almost all sequences the optimum is of order n log n for n lookups, which any balanced tree achieves, so the missing step is an understanding of the "easy" sequences [6]. Wilber's lower bounds on the optimum are, in Demaine and colleagues' words, "complex functions" of the sequence [3]. A resolution would be a proof that splay trees are within a constant factor of the optimum on every sequence, or sequences on which they are not. No prize sets the bar.
What is known
Splay trees (1985–2000). Sleator and Tarjan proved that splay trees take amortised O(log n) time per operation and, on long enough sequences, are as efficient as the best fixed tree to within a constant factor [1]. Their working set theorem bounds the time of an access by the logarithm of one plus the number of different items accessed since the item was last accessed [1]. Later work added bounds for sequential access and for accesses near the previous one, the dynamic finger bound [1, 3]. In 2004 Demaine and colleagues noted that these bounds still allow O(log n) time per access on some sequences that splay trees serve in constant time, so that no binary search tree was known to be better than O(log n)-competitive, that is, within a factor O(log n) of the optimum [3].
Lower bounds (1989–2020). Robert Wilber gave two methods for bounding from below the cost of any binary search tree, even one that knows the whole sequence in advance; for example, the bit-reversal permutation requires Θ(n log n) time [2]. In 2009 Demaine, Harmon, Iacono, Daniel Kane and Pătraşcu showed that executions of binary search trees correspond exactly to sets of points in the plane that are "arborally satisfied": every rectangle spanned by two points not on a common horizontal or vertical line contains a further point [4]. From this view they derived a lower bound that subsumes both of Wilber's [4]; in Iacono's 2013 survey this independent rectangle bound is the best known lower bound on the optimum [5]. In 2020 Victor Lecomte and Omri Weinstein proved that Wilber's funnel bound dominates his alternation (interleave) bound on every sequence and exceeds it by a factor of Θ(log log n) on some [8].
Competitive trees (2004–2023). The Tango tree of Demaine, Harmon, Iacono and Pătraşcu is O(log log n)-competitive, the first major progress on the conjecture [3]. A greedy offline algorithm, proposed by Joan M. Lucas in 1988 and by J. Ian Munro in 2000, rearranges each search path to suit future accesses [4, 11]. Demaine and colleagues showed in 2009 that an online algorithm can match its cost, so that Greedy became the first proposal for dynamic optimality not based on splay trees [4]. In 2023 Yaniv Sadeh and Haim Kaplan proved that Greedy's competitive ratio is at least 2 and that its additive gap to the optimum can be Ω(m log log n) for m accesses, against an earlier conjecture that the gap is only linear in m [9].
Special cases (2015–2022). Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn and Thatchaphol Saranurak noted in 2015 that no online tree was known to satisfy Sleator and Tarjan's traversal conjecture, that accessing the keys in the preorder of another tree takes linear time; they proved that Greedy is almost linear on such sequences, and linear with linear-time preprocessing [1, 6]. Caleb Levy and Tarjan showed that splaying is dynamically optimal if and only if it is approximately monotone, meaning that removing lookups from a sequence raises its cost by at most a fixed factor, and they prove the property for a lower bound on the optimum [7].
Recent claims (2026). On 20 July 2026 Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký and Tarjan posted a preprint claiming that splay trees are O(log log n · log² log log n)-competitive, the first ratio below O(log n) for splay trees [10]. Instead of comparing with a lower bound, they charge the cost directly to the optimal tree, and they prove the split conjecture, that any sequence of splits takes linear total time, up to a similar factor [10]. On 5 August 2026 Yuhao Guo, Seth Pettie, Daniel Skora and Chengzhang Wan posted a preprint, independent of the first, claiming that Greedy is 2^(O(√(log log n)))-competitive, the first non-trivial bound for Greedy [11]. Both are preprints, not peer reviewed; on 15 October 2026 arXiv listed no journal or conference version for either [10, 11]. Neither claims a constant ratio, and the first states that no binary search tree algorithm is known to be dynamically optimal, so the conjecture remains open [10, 11].
Main approaches
Tracking a lower bound. Build a tree whose cost stays within a known factor of a lower bound on the optimum, as Tango trees do with the interleave bound [3]. Strongest evidence: O(log log n)-competitive trees built this way, from Tango onwards [3, 10]. Main difficulty: the interleave bound can fall below the optimum by a factor of order log log n, so this line of analysis cannot prove dynamic optimality [3, 10]. Stronger lower bounds exist [4, 8], and Lecomte and Weinstein describe their 2020 result as the first progress on Wilber's conjecture that the funnel bound matches the optimum [8].
Analysing splay trees directly. Prove that splaying is constant-competitive. Strongest evidence: static optimality, the working set and related theorems [1, 3], and the 2026 preprint's Õ(log log n) ratio [10]. Main difficulty: restricted forms such as the traversal conjecture are still proved only for special cases [6, 11], and Levy and Tarjan had not proved approximate monotonicity for splaying in their 2022 version [7].
Greedy and the geometric view. Study Greedy as a rule for adding points to a point set, where it is simple to describe [4, 11]. Strongest evidence: upper bounds on pattern-avoiding sequences that were not known for any other online tree [6], and the 2026 preprint's bound [11]. Main difficulty: Greedy is at best 2-competitive, and the stronger conjecture that it is optimal up to an additive O(m) is false [9, 11].
Combining algorithms. Build one online tree that does as well as the best of many candidates. Strongest evidence: Iacono's algorithm OnOpt, built with methods from learning theory, is dynamically optimal, up to an additive term depending on n, if any online tree is; and a constant number of online trees can be combined, subject to technical conditions [5]. Main difficulty: OnOpt is, in Iacono's words, "decidedly not in the real-world BST model", and combining more than a constant number of trees was an open problem in 2013 [5].
Open sub-questions
- The extra factor. Can the log² log log n factor in Chmel et al.'s bound for splay trees be removed, to match the O(log log n) of Tango trees [3, 10]?
- Greedy's ratio. Can Guo et al.'s 2^(O(√(log log n))) bound for Greedy be improved to O(log log n), the order of the 2026 bound for splay trees [10, 11]?
- Funnel against rectangles. Is Wilber's funnel bound within a constant factor of the independent rectangle bound on every sequence, as Lecomte and Weinstein's result for sequences with constant funnel bound suggests [4, 8]?
- Traversal. Does splaying the keys of a tree in the preorder of another tree take O(n) time, Sleator and Tarjan's traversal conjecture [1, 6]?
- Monotonicity. Is splaying approximately monotone, which Levy and Tarjan show is equivalent to its dynamic optimality [7]?
- The offline optimum. Can the optimal cost of a given sequence be approximated within a constant factor in polynomial time, Demaine et al.'s Open Problem 1.1 [4]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Sleator, D. D. & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM 32(3), 652–686. 10.1145/3828.3835 · Checked 15 Oct 2026
- Wilber, R. (1989). Lower bounds for accessing binary search trees with rotations. SIAM Journal on Computing 18(1), 56–67. 10.1137/0218004 · Checked 15 Oct 2026
- Demaine, E. D., Harmon, D., Iacono, J. & Pătraşcu, M. (2004). Dynamic optimality—almost. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), 484–490; journal version in SIAM Journal on Computing 37(1), 240–251 (2007), DOI 10.1137/S0097539705447347. 10.1109/FOCS.2004.23 · Checked 15 Oct 2026
- Demaine, E. D., Harmon, D., Iacono, J., Kane, D. & Pătraşcu, M. (2009). The geometry of binary search trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 496–505. 10.1137/1.9781611973068.55 · Checked 15 Oct 2026
- Iacono, J. (2013). In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms, Lecture Notes in Computer Science, Springer, 236–250. 10.1007/978-3-642-40273-9_16 · Checked 15 Oct 2026
- Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T. (2015). Pattern-avoiding access in binary search trees. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), 410–423. 10.1109/FOCS.2015.32 · Checked 15 Oct 2026
- Levy, C. C. & Tarjan, R. E. (2019). A foundation for proving splay is dynamically optimal. Preprint, arXiv:1907.06310 (version 3, 9 May 2022); an earlier version appeared as "A new path from splay to dynamic optimality" in the Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 1311–1330, DOI 10.1137/1.9781611975482.80. Source · Checked 15 Oct 2026
- Lecomte, V. & Weinstein, O. (2020). Settling the relationship between Wilber's bounds for dynamic optimality. In 28th Annual European Symposium on Algorithms (ESA 2020), Leibniz International Proceedings in Informatics 173, 68:1–68:21. 10.4230/LIPIcs.ESA.2020.68 · Checked 15 Oct 2026
- Sadeh, Y. & Kaplan, H. (2023). Dynamic binary search trees: improved lower bounds for the Greedy-Future algorithm. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Leibniz International Proceedings in Informatics 254, 53:1–53:21. 10.4230/LIPIcs.STACS.2023.53 · Checked 15 Oct 2026
- Chmel, P., Haeupler, B., Hladík, R., Koucký, M., Roeyskoe, A., Rozhoň, V., Sladký, O. & Tarjan, R. E. (2026). Splay trees are almost dynamically optimal. Preprint, arXiv:2607.18498 (version 1, 20 July 2026), not peer reviewed. Source · Checked 15 Oct 2026
- Guo, Y., Pettie, S., Skora, D. & Wan, C. (2026). The Greedy binary search tree is non-trivially competitive. Preprint, arXiv:2608.04410 (version 1, 5 August 2026), not peer reviewed. Source · Checked 15 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.