Splay Tree - Performance Theorems

Performance Theorems

There are several theorems and conjectures regarding the worst-case runtime for performing a sequence S of m accesses in a splay tree containing n elements.

Balance Theorem
The cost of performing the sequence S is . In other words, splay trees perform as well as static balanced binary search trees on sequences of at least n accesses.
Static Optimality Theorem
Let be the number of times element i is accessed in S. The cost of performing S is . In other words, splay trees perform as well as optimum static binary search trees on sequences of at least n accesses.
Static Finger Theorem
Let be the element accessed in the access of S and let f be any fixed element (the finger). The cost of performing S is .
Working Set Theorem
Let be the number of distinct elements accessed between access j and the previous time element was accessed. The cost of performing S is .
Dynamic Finger Theorem
The cost of performing S is .
Scanning Theorem
Also known as the Sequential Access Theorem. Accessing the n elements of a splay tree in symmetric order takes O(n) time, regardless of the initial structure of the splay tree. The tightest upper bound proven so far is .

Read more about this topic:  Splay Tree

Famous quotes containing the word performance:

    The honor my country shall never be stained by an apology from me for the statement of truth and the performance of duty; nor can I give any explanation of my official acts except such as is due to integrity and justice and consistent with the principles on which our institutions have been framed.
    Andrew Jackson (1767–1845)