Editing Splay tree (section)

== Dynamic optimality conjecture ==

{{Main article|Optimal binary search tree}}
{{unsolved|computer science|Do splay trees perform as well as any other binary search tree algorithm?}}
In addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original Sleator and Tarjan paper.  This conjecture is known as the ''dynamic optimality conjecture'' and it basically claims that splay trees perform as well as any other binary search tree algorithm up to a constant factor.

:'''Dynamic Optimality Conjecture:<ref name="SleatorTarjan" />''' Let <math>A</math> be any binary search tree algorithm that accesses an element <math>x</math> by traversing the path from the root to <math>x</math> at a cost of <math>d(x)+1</math>, and that between accesses can make any rotations in the tree at a cost of 1 per rotation.  Let <math>A(S)</math> be the cost for <math>A</math> to perform the sequence <math>S</math> of accesses.  Then the cost for a splay tree to perform the same accesses is <math>O[n + A(S)]</math>.

There are several corollaries of the dynamic optimality conjecture that remain unproven:

:'''Traversal Conjecture:<ref name="SleatorTarjan" />''' Let <math>T_1</math> and <math>T_2</math> be two splay trees containing the same elements.  Let <math>S</math> be the sequence obtained by visiting the elements in <math>T_2</math> in preorder (i.e., depth first search order).  The total cost of performing the sequence <math>S</math> of accesses on <math>T_1</math> is <math>O(n)</math>.

:'''Deque Conjecture:<ref name="Tarjan" /><ref name="Pettie">{{harvnb|Pettie|2008}}.</ref><ref name="Sundar">{{harvnb|Sundar|1992}}.</ref>''' Let <math>S</math> be a sequence of <math>m</math> [[double-ended queue]] operations (push, pop, inject, eject).  Then the cost of performing <math>S</math> on a splay tree is <math>O(m + n)</math>.

:'''Split Conjecture:<ref name="Lucas">{{harvnb|Lucas|1991}}.</ref>''' Let <math>S</math> be any permutation of the elements of the splay tree.  Then the cost of deleting the elements in the order <math>S</math> is <math>O(n)</math>.