AVL Tree Rotations: Balance Factors, LL/RR/LR/RL, Traced Step by Step

The invariant: balance factor within ±1

For each node, define height (longest path to a leaf, leaf height = 1, empty subtree = 0) and

balance factor BF(node) = height(left) − height(right).

The AVL property is BF ∈ {−1, 0, +1} for every node. That local rule is what bounds the whole tree's height at 1.44 · log₂(n+2) — i.e., O(log n) — which is the entire point: search, insert and delete stay logarithmic guaranteed, unlike a plain BST that can degenerate into a linked list.

Two facts to hold onto before the mechanics: BF is computed from heights, so heights must be correct before anything is judged; and an imbalance is always repaired at the lowest offending node first — fixing there usually fixes everything above.

struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    int height = 1;                // leaf: 1  (nullptr treated as 0)
};

int h(Node* n) { return n ? n->height : 0; }
void update(Node* n) { n->height = 1 + std::max(h(n->left), h(n->right)); }
int bf(Node* n) { return h(n->left) - h(n->right); }

Rotations: the single rotation, traced

A rotation is a three-pointer rewrite that swaps a parent with one of its children while preserving BST order. The right rotation at node z lifts z's left child x above z:

        z                x
       / \              / \
      x   T3    ==>    T1  z
     / \                  / \
    T1  T2               T2  T3

Inorder sequence T1 < x < T2 < z < T3 is identical before and after — that is the property that makes rotations safe. The left rotation is the mirror image. Trace the pointers once, slowly:

1. z->left = x->right — T2 moves from x's right to z's left.
2. x->right = z — z drops below x.
3. update(z) then update(x) — z is now the lower node, so its height must be recomputed first.
4. Return x as the new subtree root; the caller (recursion) reattaches it where z used to be.

Node* rotateRight(Node* z) {
    Node* x = z->left;
    z->left = x->right;           // T2 moves to z
    x->right = z;                 // z drops below x
    update(z);                    // lower node FIRST
    update(x);
    return x;
}
Node* rotateLeft(Node* z) {       // mirror image
    Node* x = z->right;
    z->right = x->left;
    x->left = z;
    update(z);
    update(x);
    return x;
}

The four cases: LL, RR, LR, RL

After an insert, walk back up the recursion updating heights. At the first node z with |BF| = 2, look at the direction of the two steps from z toward the newly inserted node:

LL (the straight line). Insert 5 into 10 ← 8 ← 6: tree 10(8(6)). BF(10) = +2, path left-left. One right rotation at 10 → 8(6, 10). Balanced.

LR (the zig). Insert 9 into 10(8(_, 9)): path from 10 is left (to 8), then right (to 9). A single right rotation at 10 would give 9(8(_, _), 10) — wait: rotating right with x = 8 makes 8 the root and 9 its right-right chain, leaving BF(8) = −2 still unbalanced. The correct repair: left-rotate at 8 first (9 lifts above 8: 10(9(8)) — an LL shape), then right-rotate at 10 → 9(8, 10). Balanced.

RR and RL are the exact mirrors. The mnemonic to trust under pressure: a zig needs two rotations, a straight line needs one; the middle value of the three ends up as the subtree root.

The repair, in code

Insertion is BST descent, then the recursive return path does all the AVL work — update height, judge BF, repair:

After the four cases, BF(z) is back in range, and — the insertion theorem — one repair at the lowest offender restores the whole tree's height to what it was before the insert, so at most one rotation (single or double) happens per insertion. Deletion is crueler: a repair can shorten a subtree, re-exposing an ancestor, so deletion can cascade O(log n) rotations on the way back up — a classic distinguisher question.

Node* rebalance(Node* z) {
    update(z);
    if (bf(z) == 2) {                        // left-heavy
        if (bf(z->left) < 0)                 // LR: zig
            z->left = rotateLeft(z->left);
        return rotateRight(z);               // LL or LR's second half
    }
    if (bf(z) == -2) {                       // right-heavy
        if (bf(z->right) > 0)                // RL: zig
            z->right = rotateRight(z->right);
        return rotateLeft(z);                // RR or RL's second half
    }
    return z;                                // still balanced
}

Node* insert(Node* n, int key) {
    if (!n) return new Node{key};
    if (key < n->key)  n->left  = insert(n->left,  key);
    else if (key > n->key) n->right = insert(n->right, key);
    else return n;                           // duplicate: ignore
    return rebalance(n);
}

The mistakes that cost marks

• Judging BF before updating heights. The freshly changed subtree's height is stale until update(z) runs; checking BF on stale heights skips the repair entirely. Order is: update, then judge.
• Updating the rotation's heights in the wrong order. After lifting x above z, update(z) must run before update(x) — x's new height depends on z's corrected one. Reversed, every height above is wrong by one.
• Reading LR/RL as a single new rotation. Double rotations are two standard rotations with a specific order; writing one bespoke pointer shuffle loses the inorder argument and usually the marks.
• Choosing the case from BF(z) alone. LL and LR both give BF(z) = +2; the child's BF is what separates them. Same for −2 (RR vs RL).
• Forgetting the deletion cascade. "At most one rotation per operation" is true for insertion only; deletion may rotate at every level back up to the root.

Exercises with solutions

Work through each question before opening the solution below it.

Related pages