The dynamic optimality conjecture for splay trees
For a sequence of accesses to keys in a binary search tree with keys, let be the minimum total cost of serving by any binary search tree algorithm that may rotate the tree, even one that knows in advance. Prove or disprove that splay trees serve every access sequence with cost .
History and references
Still open as of 2026.
Sleator and Tarjan introduced splay trees in 1985. A splay tree moves each accessed key to the root by a specific sequence of rotations and stores no balance information at all. They proved that splay trees are within a constant factor of the best static tree for any access sequence and conjectured that the same holds against the best dynamic tree. Several consequences of the conjecture, such as the working set and dynamic finger properties, have been proved on their own. The best competitive ratio known for any binary search tree is , achieved by the tango trees of Demaine, Harmon, Iacono and Pătrașcu in 2004, and no online binary search tree is known to be -competitive.
References
Solutions 0
Sign in or create an account to publish a solution