Zig, Zig-Zig, and Zig-Zag Cases
What you'll learn: The three specific rotation patterns that make splaying work in splay trees.
When you perform a splaying operation (moving a node toward the root), you repeatedly apply one of three transformation cases based on the node's position relative to its parent and grandparent. Think of these as dance moves that shuffle nodes up the tree.
The Three Cases
Zig (terminal case): This happens when your target node is one step away from the root—it's a direct child of the root. You perform a single rotation (left or right) to bring the node to the top. This is the simplest case and only occurs as the final step of splaying.
Zig-Zig (line case): Your target node, its parent, and its grandparent form a straight line—all three are either left children or all right children. You rotate the grandparent first, then the parent. This "unzips" the chain efficiently.
Zig-Zag (triangle case): Your target node zig-zags relative to its ancestors—for example, it's a left child of a right child, or vice versa. You rotate the target twice: first around its parent, then around what was its grandparent. This is similar to AVL double rotations.
Why Three Cases?
The distinction between zig-zig and zig-zag is crucial for splay trees' performance. The zig-zig case ensures recently accessed deep nodes bring their nearby neighbors closer to the root, maintaining the amortized efficiency that makes splay trees special. If you always used single rotations (like basic "rotate to root"), you wouldn't get this balancing property.
Key Takeaway: Splaying uses three cases—zig (single rotation at root), zig-zig (double rotation on a line), and zig-zag (double rotation on a triangle)—to efficiently move accessed nodes to the root while restructuring the tree.