Structural Rotation

We need a way to repair an unbalanced node without disturbing the search order. To see what a repair looks like, take the smallest tree that can become unbalanced: three values.

Insert 3, 5, and 7 into a binary search tree. The shape depends on the order they arrive in. When 5 comes first, we get the balanced tree:

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

Both orders 5, 3, 7 and 5, 7, 3 produce this same tree. The other four orders do not. In two of them, every node has its child on the same side, so the tree is a straight spine.

From 3, 5, 7, a spine of right children:

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

From 7, 5, 3, a spine of left children:

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

In the other two, the direction changes at the middle node, so the tree has a bent shape.

From 3, 7, 5:

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

From 7, 3, 5:

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

That is five different shapes, all made from the same three values. Last chapter we saw that reading a binary search tree in order always lists its values from smallest to largest. So reading any of these five in order gives the same list: 3, 5, 7. Shape and order are separate things.

So we can take any of the four unbalanced trees and reshape it into the balanced one without breaking the order. That reshaping is a structural rotation: an operation that changes a tree’s shape without changing the order its values are read in.

These trees have only three nodes each. Later, the same rotations will have to work when these nodes have full subtrees below them.