Rotations by Hand

A rotation changes the shape of a subtree around one node. A right rotation moves the node’s left child up into the node’s place, and a left rotation moves the node’s right child up.

Solution

40 rises into 60’s place, and 60 becomes 40’s right child. 40’s old right child, 50, moves over to become 60’s left child:

                ╭────╮
                │ 40 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 20 │                │ 60 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 10 │    │ 30 │      │ 50 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯
Solution

It leaves the in-order sequence unchanged: reading the values in order gives the same sorted list before and after. A binary tree is a binary search tree exactly when its in-order sequence is sorted, so the rotated subtree is still a binary search tree. It also holds the same values as before, so every value is still on the correct side of every ancestor above it.

Solution

First, a left rotation at 90’s left child 30. 60 rises, 30 becomes its left child, and 60’s old left child 50 becomes 30’s right child:

                          ╭────╮
                          │ 90 │
                          ╰──┬─╯
                 ┌───────────┴───────────┐
              ╭──┴─╮                  ╭──┴─╮
              │ 60 │                  │ 95 │
              ╰──┬─╯                  ╰────╯
        ┌────────┴────────┐
     ╭──┴─╮            ╭──┴─╮
     │ 30 │            │ 70 │
     ╰──┬─╯            ╰────╯
   ┌────┴────┐
╭──┴─╮    ╭──┴─╮
│ 20 │    │ 50 │
╰────╯    ╰────╯

Then a right rotation at 90. 60 rises to the top, 90 becomes its right child, and 60’s old right child 70 becomes 90’s left child:

                ╭────╮
                │ 60 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 90 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 50 │      │ 70 │    │ 95 │
╰────╯    ╰────╯      ╰────╯    ╰────╯