Tracing a Full Sequence

We will insert 1 through 7 in order into an AVL tree. That is sorted input, the kind that built a degenerate tree in the search tree chapter: seven values added in increasing order formed a single chain of height $6$.

After each insertion, follow the path back up from the new leaf and check the balance factor of every node on it.

Insert 1. The tree is a single node:

╭───╮
│ 1 │
╰───╯

Insert 2. It goes to the right of 1. The root 1 has a balance factor of $-1$, which is allowed:

╭───╮
│ 1 │
╰─┬─╯
  └───┐
    ╭─┴─╮
    │ 2 │
    ╰───╯

Insert 3. It goes to the right of 2. Now the root 1 has a balance factor of $-2$:

╭───╮
│░1░│  ◀── bf = -2
╰─┬─╯
  └───┐
    ╭─┴─╮
    │ 2 │
    ╰─┬─╯
      └───┐
        ╭─┴─╮
        │ 3 │
        ╰───╯

1 is right-heavy, and its right child 2 is right-heavy too. That is a straight spine, so a single left rotation at 1 fixes it. 2 rises to the top:

     ╭───╮
     │░2░│
     ╰─┬─╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 1 │     │ 3 │
╰───╯     ╰───╯

Insert 4. It goes to the right of 3. On the path back up, 3 has a balance factor of $-1$ and the root 2 has $-1$. Both are allowed, so nothing rotates:

      ╭───╮
      │ 2 │
      ╰─┬─╯
  ┌─────┴─────┐
╭─┴─╮       ╭─┴─╮
│ 1 │       │ 3 │
╰───╯       ╰─┬─╯
              └───┐
                ╭─┴─╮
                │ 4 │
                ╰───╯

Insert 5. It goes to the right of 4. Follow the path back up from 5. 4 has a balance factor of $-1$, which is allowed. 3 has a balance factor of $-2$:

       ╭───╮
       │ 2 │
       ╰─┬─╯
  ┌──────┴──────┐
╭─┴─╮         ╭─┴─╮
│ 1 │         │░3░│  ◀── bf = -2
╰───╯         ╰─┬─╯
                └───┐
                  ╭─┴─╮
                  │ 4 │
                  ╰─┬─╯
                    └───┐
                      ╭─┴─╮
                      │ 5 │
                      ╰───╯

The root 2 is also unbalanced, but we do not mark it yet. We follow the path back up from the new leaf, and as soon as we find an unbalanced node, we apply a rotation to fix it. Here that node is 3. It is right-heavy, and so is its right child 4, another straight spine. A single left rotation at 3 lifts 4:

        ╭───╮
        │ 2 │
        ╰─┬─╯
  ┌───────┴───────┐
╭─┴─╮           ╭─┴─╮
│ 1 │           │░4░│
╰───╯           ╰─┬─╯
             ┌────┴────┐
           ╭─┴─╮     ╭─┴─╮
           │ 3 │     │ 5 │
           ╰───╯     ╰───╯

That one repair also fixed 2. Its right subtree is back to height $1$, so its balance factor is $-1$, and it is not unbalanced anymore. The next page shows why, after an insertion, repairing the lowest unbalanced node is always enough.

Insert 6. It goes to the right of 5. On the path back up, 5 and 4 each have a balance factor of $-1$. The root 2 has $-2$: its left subtree has height $0$ and its right subtree has height $2$:

          ╭───╮
          │░2░│  ◀── bf = -2
          ╰─┬─╯
  ┌─────────┴─────────┐
╭─┴─╮               ╭─┴─╮
│ 1 │               │ 4 │
╰───╯               ╰─┬─╯
                ┌─────┴─────┐
              ╭─┴─╮       ╭─┴─╮
              │ 3 │       │ 5 │
              ╰───╯       ╰─┬─╯
                            └───┐
                              ╭─┴─╮
                              │ 6 │
                              ╰───╯

2 is right-heavy, and its right child 4 is right-heavy too. A single left rotation at 2 lifts 4 to the root:

             ╭───╮
             │░4░│
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 2 │           │ 5 │
     ╰─┬─╯           ╰─┬─╯
  ┌────┴────┐          └───┐
╭─┴─╮     ╭─┴─╮          ╭─┴─╮
│ 1 │     │ 3 │          │ 6 │
╰───╯     ╰───╯          ╰───╯

4 already had a left child, 3. When 4 rises, 3 cannot stay there, because 2 is now 4’s left child. 3 is larger than 2 and smaller than 4, so it moves over to become 2’s right child, the spot that 4 left empty.

Insert 7. It goes to the right of 6. 6 has a balance factor of $-1$, but 5 has $-2$:

              ╭───╮
              │ 4 │
              ╰─┬─╯
       ┌────────┴────────┐
     ╭─┴─╮             ╭─┴─╮
     │ 2 │             │░5░│  ◀── bf = -2
     ╰─┬─╯             ╰─┬─╯
  ┌────┴────┐            └───┐
╭─┴─╮     ╭─┴─╮            ╭─┴─╮
│ 1 │     │ 3 │            │ 6 │
╰───╯     ╰───╯            ╰─┬─╯
                             └───┐
                               ╭─┴─╮
                               │ 7 │
                               ╰───╯

5 is right-heavy, and its right child 6 is right-heavy too. One more single left rotation, at 5, lifts 6:

                ╭───╮
                │ 4 │
                ╰─┬─╯
       ┌──────────┴──────────┐
     ╭─┴─╮                 ╭─┴─╮
     │ 2 │                 │░6░│
     ╰─┬─╯                 ╰─┬─╯
  ┌────┴────┐           ┌────┴────┐
╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
│ 1 │     │ 3 │       │ 5 │     │ 7 │
╰───╯     ╰───╯       ╰───╯     ╰───╯

After seven insertions in sorted order, the tree has height $2$. Every imbalance here was a right-right case. Each new value was larger than all the values before it, so it landed on the far right. A single left rotation repaired the imbalance each time.