A splay tree is a normal binary search tree (BST) in all outward respects. The difference is that the standard tree operations--insert, delete, and find--are implemented in terms of an operation called SPLAY.
The easiest way to describe the SPLAY operation is by example. Suppose you want to find a particular key K in a tree (assume K is in the tree). The first step is to search for K in the tree. SPLAY locates the node by performing a normal tree traversal.
Now comes the weird part. Instead of just returning K, SPLAY promotes it to the root of the tree via a series of operations called "rotations." Find then returns the root of the tree. These rotations reorganize the tree such that skewed trees tend to become bushier and therefore more balanced. The node containing the target of the search is now at the root of the tree, so the next time you go looking for it, it'll be waiting right near the top.
That's the real reason for splay trees; frequently accessed data stays near the root of the tree, so most accesses are very fast. Suppose a bank kept its customer database in a splay tree. Frequent customers would tend to be near the root of the tree, while inactive customers would be located near the leaves. Since records for frequent customers are accessed more often, overall performance is improved.
At the same time, SPLAY tends to balance skewed trees. A splay tree is not a balanced tree in the sense that height balancing is one of its invariants, and it can have any shape (even all left or all right children, just like a BST. Nevertheless, for any sequence of k insert, delete and find operations, on a tree of size N, splay trees guarantee that we'll do O(k lg N) work.
Hold it. If a splay tree can be just as skewed as a BST, why isn't its worst case O(n), like the BST? Because the splay tree adjusts itself. In fact, the O(k lg N) bound for the splay tree is shown not through traditional worst-case analysis but by using amortized analysis. Amortized analysis deals with sequences of operations instead of focusing on a single horrible situation like traditional techniques.
Rather than showing a formal proof, let's see if we can get a feel for the splay tree's behavior by comparing it to a plain vanilla binary search tree. The worst thing that can happen in a BST is for all nodes to end up on either the left or right side. If we access the very bottom node, we pay O(n). We could do that forever, paying the same price each time. We also pay O(n) (worst case) to build our unfortunate tree in the first place. Overall cost: O(n).
What if we try the same thing with the splay tree? First of all, in order to get a linear tree, all the nodes must have gone to the root of the tree, so we only pay O(1) for each insert, not O(n), as is the worst case for the ordinary BST. Now, finding the very bottom node of a linear splay tree is about the same amount of work as finding it in a BST. But since all the inserts were so cheap, on the whole we've done much less than O(n) work--in fact, just about O(lg n).
Furthermore, since finding the bottom node means we "splayed" the tree, the whole tree is no longer linear. In fact, it's about half as deep as it was, so if we go get the deepest node again, it's only half as far to go, which again reduces the tree depth, and so on. Eventually, the tree is just about balanced, and all finds take about O(lg n) work.
The gist of the splay tree analysis is that some operations are worse than lg n, and some are better. For any possible combination of operations, the good ones always balance the bad ones to result in O(lg n) overall behavior.
In a splay tree, the find operation is implemented as a SPLAY operation to promote the node to the root. The find operation then simply returns the root of the tree (assuming the node is in the tree). The other common BST operations, delete and insert, are implemented similarly. For insert, the tree is traversed to find the right place for the new node, a normal insert is performed, and then SPLAY is called to promote the new node to the root.Figure 1 illustrates the insert operation.
Deleting is slightly more complex. First, perform a SPLAY on the node to be deleted; this promotes the node to the root. Delete the node; this leaves you with two orphaned subtrees. Pick one of the subtrees (say the left one) and again SPLAY on the node just deleted. Of course the node won't be found; you'll get the in-order successor or predecessor to the node, which becomes the new root of the tree. Because everything in the right orphaned subtree must be greater than everything in the left orphaned subtree, the right subtree is simply attached to the new root. Delete therefore requires two splayings on the tree. Figure 2 illustrates a delete operation.
The basis of splaying is the rotations that bring the target node to the root. Three kinds of rotations correspond to three patterns of subtrees consisting of the key node, its parent, and its grandparent. The rotations are called zig, zig-zig, and zig-zag.
The zig rotation is easiest and can only occur when the key node's parent is the root of the tree. This is illustrated in Figure 3, where K is the key node and P is the parent. For the zig-zig and zig-zag rotations, the key node has both a parent and grandparent. If the key node K is the left child of a left child, then a zig-zig rotation is called for, as shown in Figure 4. Finally, if the key is the right child of a left child, then we do a zig-zag rotation; see Figure 5.
Each rotation has its mirror twin: That is, we also zig when the key is the right child of the root, zig-zig for a right child of a right child, and zig-zag for a left child of a right child.
It's easy to see that a zig-zag rotation tends to make the tree more balanced. It's not as readily apparent that the other rotations help the balancing as well. Let's try an example.
Assume we have a BST with all left children and we want to find the left-most child. Performing a SPLAY on node 1 results in the intermediate steps shown in Figure 6.
It's not readily apparent from an example with only nine nodes, but the resulting tree is roughly half as deep as the original. Notice also that only zig-zig rotations were necessary.
Splay trees are one example of a self-adjusting data structure, a kind of data structure that rearranges itself in response to changing program operations. They're easy to code and maintain, have low overhead, and can really improve performance for data-access situations that are heavily skewed but not predictably so.
Moret, Bernard M.E. and Henry D. Shapiro. Algorithms from P to NP. vol. 1. Redwood City, CA: Benjamin Cummings, 1991.
Sleator, Daniel D. and Robert E. Tarjan. "Self-Adjusting Binary Search Trees." Journal of the ACM (July, 1985).
Weiss, Mark A. Data Structures and Algorithm Analysis. Redwood City, CA: Benjamin Cummings, 1992.