Splay Tree - Dynamic Optimality Conjecture

Dynamic Optimality Conjecture

List of unsolved problems in 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: 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:

    “Knowledge about life is one thing; effective occupation of a place in life, with its dynamic currents passing through your being, is another.”
    —William James (1842–1910)

    “What these perplexities of my uncle Toby were,—’tis impossible for you to guess;Mif you could,—I should blush ... as an author; inasmuch as I set no small store by myself upon this very account, that my reader has never yet been able to guess at any thing. And ... if I thought you was able to form the least ... conjecture to yourself, of what was to come in the next page,—I would tear it out of my book.”
    —Laurence Sterne (1713–1768)