There are some interesting data structures that use tree rotations to improve performance, but do not maintain strict balance properties. Instead, they offer looser, probabilistic guarantees of performance. One such structure is the splay tree, which uses rotations to move nodes to the root position as they are accessed. Any time we access a node (whether for lookup, insertion, or deletion), we perform a series of rotations to splay that node to the root of the tree.
To perform a splay operation, we use a series of tree rotations based on the position of the target node relative to its parent and grandparent. There are three cases to consider:
Zig: The target node is a child of the root. We perform a single rotation (left or right) to bring it to the root.
Zig-Zig: The target node and its parent are both left children or both right children. We perform two rotations in the same direction (first on the parent, then on the grandparent) to bring the target node to the root.
Zig-Zag: The target node is a left child and its parent is a right child, or vice versa. We perform two rotations in opposite directions (first on the target node, then on the grandparent) to bring the target node to the root.
When inserting a new value into a splay tree, we first perform a standard binary search tree insertion. After the new node is added as a leaf, we then splay that new node to the root. When removing a node, we first splay the target node to the root. Then, we remove the root node and merge the left and right subtrees back together. This is typically done by finding the maximum node in the left subtree and splaying it to the root of the left subtree. We can then attach the right subtree as the right child of this new root.
The splay tree is set to find 211. Step through the process to see how the tree restructures itself using rotations to bring the accessed node to the root.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Note that bringing 211 to root also pulls its nearby nodes (like 225) closer to the root as well. This is beneficial if those nodes are likely to be accessed soon after 211. Splay trees are particularly effective when there is a non-uniform access pattern and we tend to access the same nodes, or nearby nodes, multiple times in a short period.
In this particular case, the splay operation made the overall tree more balanced, but that is not always the case. Sometimes the splay operation can make the tree less balanced overall. However, it can be shown that the amortized time complexity of operations on a splay tree is \(O(\log n)\text{,}\) meaning that over a sequence of operations, the average time per operation remains logarithmic.
Splay trees use rotations to move accessed nodes to the root, improving access times for frequently used nodes. While individual operations may take longer, the amortized time complexity remains \(O(\log n)\text{.}\) However, any single operation can take up to \(O(n)\) time in the worst case.
