Double Rotations

A single rotation fixes each of the two spines. It does not fix the shapes that bend in the middle.

Insert 3, 7, 5 in that order:

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

The root 3 is unbalanced, with $bf = - 2$ . 3 is right-heavy, and its right child 7 is left-heavy.

Try a single left rotation at 3. It fails:

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

The tree is still unbalanced. The rotation only moved the bend to the other side. Now 7 is left-heavy, with a balance factor of $2$ , and its left child 3 is right-heavy.

Instead, straighten the bend first. Rotate the right child 7 to the right, which lifts 5:

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

What is left is the right-right spine from earlier. A single left rotation at 3 balances the tree:

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

That two-step move is a double right-left rotation: a right rotation on the child, then a left rotation on the root. The name gives the order of the two rotations. The pattern that calls for it is the right-left case: a node becomes unbalanced because its right child’s left subtree has grown too tall.

The mirror case is the left-right bend that inserting 7, 3, 5 builds:

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

The root 7 has $bf = 2$ . Its heavy side is its left child 3, and 3’s heavy side is its right child 5: left, then right. A single right rotation at 7 would only move the bend to the other side, so we straighten it first. Rotate the left child 3 to the left, which lifts 5 and gives the left-left spine:

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

A single right rotation at 7 then gives the balanced tree. This is a double left-right rotation: a left rotation on the child, then a right rotation on the root. The pattern that calls for it is the left-right case: a node becomes unbalanced because its left child’s right subtree has grown too tall.