Splay tree dynamic optimality

Store the numbers 3, 5 and 7 in a branching search structure with 5 at the top, 3 to its left and 7 to its right. Finding 7 visits 5 and then 7. A splay tree moves the requested number to the top while keeping smaller numbers on the left and larger ones on the right; the next request for 7 finds it immediately. Does this simple adjustment keep its total search-and-rearrangement work within one fixed factor of the best tree that knows every future request, allowing initial setup overhead?[1] [2] [3]

How well can a tree rearrange itself after requests when it cannot see the future? The splay conjecture compares its total work with the best changing binary search tree that can. Such a tree stores ordered keys with smaller keys in each left branch and larger ones in each right branch. In the standard rotation model, a search costs the number of visited nodes, and each rotation costs one. For keys arranged as 6 above its left child 4 above its left child 2, a request for 2 uses a paired step: rotate 4 above 6, then 2 above 4. The result has 2 at the root, the top node, with 4 to its right and 6 to the right of 4; all key comparisons remain ordered. This is a zig-zig step, not simply rotating the requested node upward twice. For a sequence $X$ on $n$ keys, write $\mathrm{OPT}(X)$ for that future-informed comparator’s minimum cost. The target is $\mathrm{cost}_{\mathrm{splay}}(X)\le C\,\mathrm{OPT}(X)+O(n)$, for one constant $C$ independent of $n$ and $X$.[1] [2] [3]

Repeated requests for one number are only an easy example. The guarantee must hold for every request sequence, even when the pattern changes. A July 2026 preprint reports a factor that grows very slowly with the number of stored numbers; a factor that grows at all does not establish the conjectured fixed-factor guarantee.[1] [2]

The additive initialization allowance matters: an arbitrary starting tree can put the first requested key far below the root, while the comparator may start with a favourable shape. Chmel and colleagues report an almost-optimal bound with an iterated-logarithm factor multiplying the optimal cost plus initialization term. Their presentation uses a model requiring each accessed key to become the root; Appendix B relates it to the standard model within constant factors. These model comparisons do not remove the remaining size-dependent factor.[2]

Requests need not use stored numbers equally often, and the popular numbers can change. Moving recently used items closer to the top can exploit that pattern without predicting it explicitly. The conjecture asks how much knowing the future can improve this kind of adaptation: whether a rule responding to requests as they arrive loses only a fixed factor against the best paid rearrangements chosen with full foresight.[1] [3]

Rotation costs create a tradeoff: restructuring now can make later searches cheaper, but a future-informed algorithm can choose that investment with information the splay rule lacks. Proved pattern-specific bounds capture parts of this tradeoff, such as repeated recent accesses and movements among nearby keys. A constant-factor comparison would show that those local adjustments recover essentially all the advantage available within the same search-tree model, across arbitrary mixtures of patterns; it would not claim optimality among every possible data structure.[1] [2] [3]