Rotations

March 2026 · 20 min read

In the previous post we saw that AVL trees maintain a balance factor of {-1, 0, +1} at every node. When an insertion or deletion pushes some node's balance factor to +2 or -2, we need to fix it. The fix is always a rotation: a local restructuring of 2 or 3 nodes that restores balance without breaking the BST ordering.

There are exactly four cases, and once you understand the first two, the other two are just combinations.

What a Rotation Actually Does

A rotation changes the parent-child relationship between two nodes while preserving the in-order sequence. Think of it as "pulling" a child up to become the parent, and the old parent drops down to become a child.

The critical property: a rotation never changes the in-order traversal. Before and after rotation, the same keys appear in the same sorted order. It only changes the tree's shape (depth of nodes).

Right Rotation (LL Case)

When a node Z becomes unbalanced because its left child's left subtree is too tall, we do a right rotation at Z. The left child Y moves up to take Z's place, and Z becomes Y's right child.

The Setup

Node Z has balance factor +2. Its left child Y has balance factor +1 or 0 (left-heavy or balanced). The imbalance came from Y's left subtree (the "left-left" path).

What Happens Step by Step

1. Y (Z's left child) becomes the new root of this subtree.
2. Z becomes Y's right child.
3. T2 (Y's old right subtree) becomes Z's new left child. This is the tricky part. T2 has keys between Y and Z, so it's valid as Z's left child.
4. Update heights of Z first (it's now lower), then Y.

Code

TreeNode* rotateRight(TreeNode* z) {
    TreeNode* y = z->left;
    TreeNode* T2 = y->right;

    y->right = z;        // Z drops to right
    z->left = T2;        // T2 transfers

    z->height = 1 + max(height(z->left), height(z->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;  // Y is the new root
}

Left Rotation (RR Case)

The mirror of right rotation. When Z is unbalanced because its right child's right subtree is too tall, we do a left rotation at Z.

TreeNode* rotateLeft(TreeNode* z) {
    TreeNode* y = z->right;
    TreeNode* T2 = y->left;

    y->left = z;         // Z drops to left
    z->right = T2;       // T2 transfers

    z->height = 1 + max(height(z->left), height(z->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;
}

Left-Right Double Rotation (LR Case)

This is where it gets interesting. Z has bf = +2 (left-heavy), but its left child Y is right-heavy (bf = -1). A single right rotation won't fix this because the heavy subtree is on the "wrong side" of Y.

The solution: two rotations. First left-rotate at Y to straighten the zig-zag into a straight line, then right-rotate at Z.

// LR case: left-rotate child, then right-rotate node
if (bf > 1 && balance(node->left) < 0) {
    node->left = rotateLeft(node->left);   // straighten zig-zag
    return rotateRight(node);               // normal LL fix
}

Right-Left Double Rotation (RL Case)

Mirror of LR. Node Z has bf = -2, and its right child Y has bf = +1 (left-heavy). The zig-zag goes right then left.

Fix: right-rotate at Y first (straighten), then left-rotate at Z.

// RL case: right-rotate child, then left-rotate node
if (bf < -1 && balance(node->right) > 0) {
    node->right = rotateRight(node->right); // straighten zig-zag
    return rotateLeft(node);                 // normal RR fix
}

The Four Cases Cheat Sheet

Interactive: Watch All Four Rotations

Rotation Cost: O(1)

Each rotation (single or double) involves a constant number of pointer reassignments and height updates. No matter how large the tree, a rotation takes O(1) time. The expensive part of insert/delete is finding where the imbalance is (O(log n) walk), not fixing it.

What's Next

Now that we understand all four rotation cases, the next post walks through the full AVL insert and delete algorithms: how we find the imbalance, decide which rotation to apply, and update heights on the way back up the recursion.