Choosing a Rotation

The balance factor of a node is the height of its left subtree minus the height of its right subtree. An AVL tree repairs an unbalanced node, one with a balance factor of $2$ or $- 2$ , with one of four rotations: single right, single left, double left-right, or double right-left. The heavy child is the unbalanced node’s child on its taller side.

Solution

A single right rotation.
A left-right double rotation.
A single left rotation.
A right-left double rotation.
A single left rotation.

Exercise

Why does a single rotation not repair a node whose heavy child is heavy on the opposite side? Use the three-node tree below.

╭────╮
│ 10 │
╰──┬─╯
   └───┐
    ╭──┴─╮
    │ 30 │
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│ 20 │
╰────╯

Solution

A single left rotation at 10 only moves the bend to the other side. 30 ends on top with a balance factor of $2$ , with 10 as its left child and 20 as 10’s right child:

    ╭────╮
    │ 30 │
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│ 10 │
╰──┬─╯
   └───┐
    ╭──┴─╮
    │ 20 │
    ╰────╯