Dynamic Optimality Conjecture
| 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: 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 .
Read more about this topic: Splay Tree
Famous quotes containing the words dynamic and/or conjecture:
“Imagination is always the fabric of social life and the dynamic of history. The influence of real needs and compulsions, of real interests and materials, is indirect because the crowd is never conscious of it.”
—Simone Weil (1909–1943)
“There is something fascinating about science. One gets such wholesale returns of conjecture out of such a trifling investment of fact.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)