Splay Tree - Dynamic Optimality Conjecture

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 be any binary search tree algorithm that accesses an element by traversing the path from the root to at a cost of, and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let be the cost for to perform the sequence of accesses. Then the cost for a splay tree to perform the same accesses is .

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

Traversal Conjecture: Let and be two splay trees containing the same elements. Let be the sequence obtained by visiting the elements in in preorder (i.e., depth first search order). The total cost of performing the sequence of accesses on is .

Deque Conjecture: Let be a sequence of double-ended queue operations (push, pop, inject, eject). Then the cost of performing on a splay tree is .

Split Conjecture: Let be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order is .