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 .