Data Structures & Algorithms

AVL Tree Rotations Cheat Sheet (COSC 222)

Self-balancing binary search trees. When an insertion pushes a node's balance factor outside the range [−1, +1], a rotation (or two) restores balance in O(1) time. Four cases cover every imbalance.

The balance factor

An AVL tree is a binary search tree in which the heights of the two child subtrees of every node differ by at most one. The balance factor is that difference in height.

BF(node) = height(left) − height(right)
  • Balanced when |BF| ≤ 1.
  • Left-heavy when BF = +2, its left subtree is taller.
  • Right-heavy when BF = −2, its right subtree is taller.

After every insertion, walk back up from the new leaf updating balance factors until you reach the deepest node whose |BF| = 2. Rebalancing there restores |BF| ≤ 1 for every node.

Case guide

LLleft-left insertion+2RRright-right insertion−2LRleft-right insertion+2RLright-left insertion−2

+2 when the heavy path sits in z's left subtree,−2 when it sits in z's right subtree. Read the imbalance at node z.

The four rotation cases

In every case z is the deepest unbalanced node, y is z's taller child, and x is y's taller child. LL and RR need one rotation; LR and RL need two. Each diagram is labeled before and after.

LL - right rotation

Insertion in the left subtree of the left child. A single right rotation about z rebalances it. Imbalance at z: +2.

Before

z+2yT4xT3T1T2

After

yxzT1T2T3T4
  1. 01

    Find the deepest unbalanced node z, BF(z) = +2. Let y = z.left.

  2. 02

    Let x = y.left (the left-left path). Keep subtrees T1 = x.left, T2 = x.right, T3 = y.right, T4 = z.right.

  3. 03

    Perform a right rotation about z: make y the new root of this subtree.

  4. 04

    Set y.right = z, and set z.left = T3 (y's old right subtree).

  5. 05

    Keep x.left = T1, x.right = T2, z.right = T4.

  6. 06

    Update balance factors on y, z (and x if T1/T2 differ) - all become 0 or ±1.

RR - left rotation

Insertion in the right subtree of the right child. A single left rotation about z fixes it. Imbalance at z: −2.

Before

z-2T1yT2xT3T4

After

yzxT1T2T3T4
  1. 01

    Find the deepest unbalanced node z, BF(z) = −2. Let y = z.right.

  2. 02

    Let x = y.right (the right-right path). Keep T1 = z.left, T2 = y.left, T3 = x.left, T4 = x.right.

  3. 03

    Perform a left rotation about z: make y the new root of this subtree.

  4. 04

    Set y.left = z, and set z.right = T2 (y's old left subtree).

  5. 05

    Keep T1 = z.left, x.left = T3, x.right = T4.

  6. 06

    Update balance factors on y, z (and x if T3/T4 differ) - all return to 0 or ±1.

LR - left-right double rotation

Insertion in the right subtree of the left child. First left-rotate about y, then right-rotate about z. Imbalance at z: +2.

Before

z+2yT4T1xT2T3

After

xyzT1T2T3T4
  1. 01

    Find the deepest unbalanced node z, BF(z) = +2. Let y = z.left (BF(y) = −1).

  2. 02

    Let x = y.right. Subtree layout: T1 = y.left, T2 = x.left, T3 = x.right, T4 = z.right.

  3. 03

    Step 1 - left-rotate about y: x lifts to become z's left child; y becomes x's left child.

  4. 04

    After step 1, x.left = y, x.right = T3 are set; T1 stays y.left and T2 stays y.right.

  5. 05

    Step 2 - right-rotate about z: x becomes the new root.

  6. 06

    Reattach: x.right = z, z.left = T3; keep y.left = T1, y.right = T2, z.right = T4. All factors return to balance.

RL - right-left double rotation

Insertion in the left subtree of the right child. First right-rotate about y, then left-rotate about z. Imbalance at z: −2.

Before

z-2T1yxT4T2T3

After

xzyT1T2T3T4
  1. 01

    Find the deepest unbalanced node z, BF(z) = −2. Let y = z.right (BF(y) = +1).

  2. 02

    Let x = y.left. Subtree layout: T1 = z.left, T2 = x.left, T3 = x.right, T4 = y.right.

  3. 03

    Step 1 - right-rotate about y: x lifts to become z's right child; y becomes x's right child.

  4. 04

    After step 1, x.right = y, x.left = T2; T3 stays y.left and T4 stays y.right.

  5. 05

    Step 2 - left-rotate about z: x becomes the new root.

  6. 06

    Reattach: x.left = z, z.right = T2; keep T1 = z.left, y.left = T3, y.right = T4. All factors return to balance.