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:

    Kind are her answers,
    But her performance keeps no day;
    Breaks time, as dancers,
    From their own music when they stray.
    Thomas Campion (1567–1620)