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 (17671845)
Related Subjects
Related Phrases
Related Words