Single Rotations

We start with the simplest unbalanced shape. If you insert 7, 5, 3 in that order, you get a spine of left children:

    ╭───╮
    │ 7 │
    ╰─┬─╯
    ┌─┘
  ╭─┴─╮
  │ 5 │
  ╰─┬─╯
  ┌─┘
╭─┴─╮
│ 3 │
╰───╯

The root 7 has a balance factor of $2$, so 7 is the unbalanced node.

From 7, the taller side goes down to its left child 5, and then down 5’s left side again to 3. The extra height is in the left subtree of the left child.

The fix is to lift the middle value, 5, above 7. We rotate the tree to the right:

       ╭───╮
       │ 5 │
       ╰─┬─╯
    ┌────┴─────┐
  ╭─┴─╮      ╭─┴─╮
  │ 3 │      │ 7 │
  ╰───╯      ╰───╯

This is a single right rotation. The middle value 5 moves up to become the new root. The old root 7 moves down to become 5’s right child, since 7 is larger than 5. The value 3 stays on 5’s left. An in-order traversal of the new tree still gives 3, 5, 7.

We use this rotation for the left-left case: a node becomes unbalanced because its left child’s left subtree has grown too tall.

The mirror case is the spine of right children you get if you insert 3, 5, 7:

╭───╮
│ 3 │
╰─┬─╯
  └─┐
  ╭─┴─╮
  │ 5 │
  ╰─┬─╯
    └─┐
    ╭─┴─╮
    │ 7 │
    ╰───╯

The root 3 has a balance factor of $-2$, and this time the extra height is in the right subtree of the right child. This is the right-right case: a node becomes unbalanced because its right child’s right subtree has grown too tall. The repair is a single left rotation, the same move with every left and right swapped. We lift 5 above 3, and 3 comes down to become 5’s left child, which gives the same balanced tree.