Relevant Information Regarding Splay Trees
This section will only provide a brief overview of Splay Trees.
For more detailed information and analysis, see Keith Schwarz's lecture slides here, or the Wikipedia page on Splay Trees here.
Splay Tree Summary
Splay Trees are a self-balancing binary search tree designed with a philosophy that can be ascribed to the principle of locality - recently accessed nodes are likely to be accessed again in the near future. With this in mind, since we must traverse the depth of the tree to access a node, we might as well use tree rotations to bring this node to the root nearly losslessly since we will be performing equivalent asymptotic work. This way, the accessed node will be near the top for accesses in the near-future.
These rotations steps are known as splaying, and through amortized analysis, ensure an amortized cost of O(logn). However, splaying does not guarantee any height balance for the tree; a simple insertion of n sorted elements into an empty splay tree yields a splay tree of height n.
Over m operations, Splay Trees guarantee O(mlogn) worst case per operation, but some of these operations can take O(n) time.
Inserting [1,2,3,4,5] into a Splay Tree
Inserting [5,4,3,2,1] into a Splay Tree
Two distinct splay operations are shown above. This splaying propagates until x is the root of the tree.
Notice that at worst, g's depth can only increase by 2 levels per operation. Splaying ensures that elements recently accessed remain near the root for better performance if they are accessed again.
Performance Theorems
These performance theorems will be based on a sequence of n inserts into a Splay Tree at an amortized cost of O(nlogn).
The theorems will then consider a sequence of m accesses on the Splay Tree.
Static Optimality Theorem
This theorem states that Splay Trees are asymptotically equivalent to Static Optimal Binary Search Trees. However, unlike Static Optimal BST's, Splay Trees do not need to know anything about the input sequence; rebalancing through splaying optimizes frequently accessed items well enough.
Let's ignore Splay Trees for a second.
Consider a sequence of accesses on the elements of any tree.
Let f(i) be the frequency of access on an element i in the tree: f(i) = total number of accesses of element i / total number of accesses = probability of searching for i in m accesses.
If we know f(i) in advance, we can generate an optimal BST that guarantees O( -log[ f(i) ] ) worst case per individual access on element i.
Back to Splay Trees:
Unlike optimal BST's, without knowing anything about the sequence in advance, over a sufficiently large sequence, Splay Trees guarantee the same worst case bound of O( -log[ f(i) ] ) except amortized rather than single-operation worst case.
An example optimal static BST is given on the left, with the given frequencies in red.
Such a structure would take O(n^2) time to build using Knuth's Algorithm, and requires knowing frequency of access pattern in advance.
This theory says over a sequence of at least n operations, Splay Trees of any initial form will perform with the same worst case time. In fact, Splay Trees will perform even better on the more frequent items since they will be splayed to the root.
Also, if the frequencies of all elements are the same, f(i) = 1/n; so the amortized worst case access time is O(logn)
Working-Set Theorem
Consider an element i in a structure. Let r be the number of distinct elements accessed after the element i was accessed. This number r is called the working set of i.
Then, in a Splay Tree, the runtime to access this element i is:
O( log(r+2) )
This theorem effectively states that the r most recently accessed elements are easiest to access. If only a subset n' of the n elements in a Splay Tree are accessed, then the access time is proportional to that subset n' rather than the size of the tree.
The working set theorem implies the Static Optimality Theorem in an amortized sense, for sufficiently long operation sequences.
This theorem forms the basis for the Working Set Structure.