Course contentsShow
← Computer Science
Lesson 569 of 2,87213. Balanced TreesFree lesson

The Splaying Operation

Understanding the splay operation that moves a node to the root through rotations.

The Splaying Operation

What you'll learn: You'll discover how the splaying operation restructures a splay tree by moving a target node to the root through a series of specialized rotations.

What Is Splaying?

The splaying operation is the heart of splay trees. When you access (search, insert, or delete) a node, splaying moves that node all the way up to become the new root of the tree. This isn't done with random rotations—it uses a specific pattern of rotations that helps keep the tree reasonably balanced over time.

Think of it like bubbling up in water: the accessed node "bubbles" to the surface (root) by swapping places with its ancestors, but in a carefully choreographed way.

Three Splaying Cases

Splaying works differently depending on where the node is relative to its parent and grandparent:

1. Zig (Base Case)

When the node is one rotation away from the root (it's a direct child), perform a single rotation.

2. Zig-Zig

When the node and its parent are both left children OR both right children (they form a "line"), rotate the grandparent first, then the parent.

3. Zig-Zag

When the node and parent form a "triangle" (node is left child, parent is right child, or vice versa), rotate the parent first, then the new parent—similar to AVL's double rotation.

You continue applying these cases repeatedly until the target node reaches the root.

Why This Pattern Matters

Unlike just doing single rotations upward, the zig-zig and zig-zag patterns help flatten deeply nested paths, preventing the tree from staying too unbalanced. Frequently accessed nodes stay near the top, making future accesses faster—this is the "self-adjusting" magic of splay trees.

Key Takeaway: The splaying operation moves a node to the root using three rotation patterns (zig, zig-zig, zig-zag), automatically restructuring the tree to improve access times for frequently used nodes.