The standard way to achieve worst case logarithmic performance per operation in a binary search tree is by imposing a balance condition on the nodes. AVL trees, for example, force logarithmic height by making each node store its height in addition to its left/right/parent pointers. The balance condition is invariant and a rebalancing operation is necessary to restore the invariant whenever it is violated.
There is another way to obtain logarithmic performance but in an amortized sense. We do not need to impose a balance condition. Rather, the tree adjusts itself after each operation by using a restructuring heuristic. Sleator and Tarjan proposed a heuristic that achieves O(lg n) time amortized per operation (over a sequence of operations). This heuristic is the splay operation. In the remainder of this post, we shall describe how the splay operation works and provide a C/C++ implementation.
We are going to use a C++ structure to represent a node. A node stores pointers to its left/right children and to its parent. Initially, all pointers point to nothing.
In a splay tree, a node x is splayed to the root of the tree whenever it is accessed. Splaying x works by climbing the x-to-root path by following parent pointers and performing rotations. A rotation is a local restructuring operation. If x is a left child, it is rotated to the right and if it is a right child, it is rotated to the left. The following is a pictorial representation of a rotation. Here x and y are nodes and A, B and C are sub-trees (possibly null).
Rotations do not change the binary search property, i.e., inorder traversals of the tree before and after the rotation give the same output. The following function performs a right rotation.
Here is code to perform a left rotation.
The splay operation performs rotations in pairs. There are two cases to consider, a zig-zig case and a zig-zag case. Let x be the node that we want to splay and let y be its parent. The zig-zig case occurs when both x and y are left children (or both right children). The zig-zag case occurs when x is a left child and y is a right child (or x is a right child and y is a left child). If y is neither a left nor a right child (it is the root), we do a single rotation. Let us elaborate.
The following figure shows the pair of rotations performed in the zig-zig step. Here x is a left child and y is a left child (the right-right case is symmetric). The order of rotations is important, we first rotate y and then we rotate x.
The following figure shows the pair of rotations performed in the zig-zag step. Here x is a right child and y is a left child (the left-right case is symmetric). We rotate x twice
To wrap, there are two cases up to symmetry and four cases in general, and we might do one last rotation at the end if x does not have a grand-parent.
By the end of the splay operation, x becomes the root of the tree. This is very useful because nodes that are accessed frequently live near the root of the tree as a result of splay.
Now you can augment nodes with keys and use the splay operation to implement the other operations. For example, to insert a node with key k, you do a regular binary search on k to find where to insert the node, and then you splay that node to the root of the tree.
That is all for this post. Thank you for reading !
