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 audience is the most revered member of the theater. Without an audience there is no theater. Every technique learned by the actor, every curtain, every flat on the stage, every careful analysis by the director, every coordinated scene, is for the enjoyment of the audience. They are our guests, our evaluators, and the last spoke in the wheel which can then begin to roll. They make the performance meaningful.”
    —Viola Spolin (b. 1911)