Dynamic optimality conjecture

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: 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: 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>, splitting each tree into two separate trees at each deleted item, is <math>O(n)</math>.

Variants

In order to reduce the number of restructuring operations, it is possible to replace the splaying with semi-splaying, in which an element is splayed only halfway towards the root.

Another way to reduce restructuring is to do full splaying, but only in some of the access operations – only when the access path is longer than a threshold, or only in the first m access operations.

Using pointer-compression techniques, it is possible to construct a succinct splay tree.

See also

  • AVL tree
  • B-tree
  • Finger tree
  • Geometry of binary search trees
  • Iacono's working set structure
  • Link/cut tree
  • List of data structures
  • Scapegoat tree
  • Splaysort, a sorting algorithm using splay trees
  • T-tree
  • Treap
  • Tree rotation
  • Trees
  • Zipper (data structure)

Notes

References

  • NIST's Dictionary of Algorithms and Data Structures: Splay Tree
  • Implementations in C and Java (by Daniel Sleator)
  • Pointers to splay tree visualizations
  • Fast and efficient implementation of Splay trees
  • Top-Down Splay Tree Java implementation