Removal Can Rebalance Several Ancestors

After an insertion, one repair is enough. A removal can need more.

Here is a tree where that happens. It is as unbalanced as an AVL tree is allowed to be: every internal node has a balance factor of $1$.

                            ╭────╮
                            │ 45 │
                            ╰──┬─╯
                   ┌───────────┴───────────┐
                ╭──┴─╮                  ╭──┴─╮
                │ 30 │                  │ 60 │
                ╰──┬─╯                  ╰──┬─╯
           ┌───────┴───────┐           ┌───┴───┐
        ╭──┴─╮          ╭──┴─╮      ╭──┴─╮  ╭──┴─╮
        │ 20 │          │ 40 │      │ 55 │  │ 65 │
        ╰──┬─╯          ╰──┬─╯      ╰──┬─╯  ╰────╯
       ┌───┴───┐       ┌───┘       ┌───┘
    ╭──┴─╮  ╭──┴─╮  ╭──┴─╮      ╭──┴─╮
    │ 15 │  │ 25 │  │ 35 │      │ 50 │
    ╰──┬─╯  ╰────╯  ╰────╯      ╰────╯
   ┌───┘
╭──┴─╮
│ 10 │
╰────╯

We remove 65, the leaf on the far right.

The first repair

Follow the path back up from where 65 was. The first node is 60. Its left subtree, under 55, has height $1$, and its right side is now empty, with height $-1$, so its balance factor is $2$.

                            ╭────╮
                            │ 45 │
                            ╰──┬─╯
                   ┌───────────┴───────────┐
                ╭──┴─╮                  ╭──┴─╮
                │ 30 │                  │░60░│  ◀── bf = +2
                ╰──┬─╯                  ╰──┬─╯
           ┌───────┴───────┐           ┌───┘
        ╭──┴─╮          ╭──┴─╮      ╭──┴─╮
        │ 20 │          │ 40 │      │ 55 │
        ╰──┬─╯          ╰──┬─╯      ╰──┬─╯
       ┌───┴───┐       ┌───┘       ┌───┘
    ╭──┴─╮  ╭──┴─╮  ╭──┴─╮      ╭──┴─╮
    │ 15 │  │ 25 │  │ 35 │      │ 50 │
    ╰──┬─╯  ╰────╯  ╰────╯      ╰────╯
   ┌───┘
╭──┴─╮
│ 10 │
╰────╯

60 is left-heavy, and its left child 55 is left-heavy too, with a balance factor of $1$. The two are heavy on the same side, so a single right rotation at 60 fixes the imbalance:

                          ╭────╮
                          │ 45 │
                          ╰──┬─╯
                   ┌─────────┴─────────┐
                ╭──┴─╮              ╭──┴─╮
                │ 30 │              │░55░│  ◀── height 1
                ╰──┬─╯              ╰──┬─╯
           ┌───────┴───────┐       ┌───┴───┐
        ╭──┴─╮          ╭──┴─╮  ╭──┴─╮  ╭──┴─╮
        │ 20 │          │ 40 │  │ 50 │  │ 60 │
        ╰──┬─╯          ╰──┬─╯  ╰────╯  ╰────╯
       ┌───┴───┐       ┌───┘
    ╭──┴─╮  ╭──┴─╮  ╭──┴─╮
    │ 15 │  │ 25 │  │ 35 │
    ╰──┬─╯  ╰────╯  ╰────╯
   ┌───┘
╭──┴─╮
│ 10 │
╰────╯

The subtree is balanced again, but look at its height. Before the removal, the subtree at 60 had height $2$. The repaired subtree under 55 has height $1$.

The second repair

Because that subtree is now shorter, the balance factor of the node above it changes. Keep following the path up to the root 45. Its left subtree, under 30, has height $3$. Its right subtree, under 55, now has height $1$. So 45 has a balance factor of $2$:

                          ╭────╮
                          │░45░│  ◀── bf = +2
                          ╰──┬─╯
                   ┌─────────┴─────────┐
                ╭──┴─╮              ╭──┴─╮
                │ 30 │              │ 55 │
                ╰──┬─╯              ╰──┬─╯
           ┌───────┴───────┐       ┌───┴───┐
        ╭──┴─╮          ╭──┴─╮  ╭──┴─╮  ╭──┴─╮
        │ 20 │          │ 40 │  │ 50 │  │ 60 │
        ╰──┬─╯          ╰──┬─╯  ╰────╯  ╰────╯
       ┌───┴───┐       ┌───┘
    ╭──┴─╮  ╭──┴─╮  ╭──┴─╮
    │ 15 │  │ 25 │  │ 35 │
    ╰──┬─╯  ╰────╯  ╰────╯
   ┌───┘
╭──┴─╮
│ 10 │
╰────╯

45 is left-heavy, and its left child 30 is left-heavy too: 30’s left subtree has height $2$ and its right subtree has height $1$. So this is again a single right rotation, this time at 45. 30 rises to the top, 45 drops to its right, and 30’s old right child 40 moves over to become 45’s left child:

                   ╭────╮
                   │░30░│
                   ╰──┬─╯
           ┌──────────┴──────────┐
        ╭──┴─╮                ╭──┴─╮
        │ 20 │                │ 45 │
        ╰──┬─╯                ╰──┬─╯
       ┌───┴───┐           ┌─────┴─────┐
    ╭──┴─╮  ╭──┴─╮      ╭──┴─╮      ╭──┴─╮
    │ 15 │  │ 25 │      │ 40 │      │ 55 │
    ╰──┬─╯  ╰────╯      ╰──┬─╯      ╰──┬─╯
   ┌───┘               ┌───┘       ┌───┴───┐
╭──┴─╮              ╭──┴─╮      ╭──┴─╮  ╭──┴─╮
│ 10 │              │ 35 │      │ 50 │  │ 60 │
╰────╯              ╰────╯      ╰────╯  ╰────╯

Every node is balanced again.

Why removal is different

The difference from insertion is what the repair does to the subtree’s height. After an insertion, the subtree has grown by one level, and the repair takes that level back off. After a removal, the subtree has not changed height yet. The removal shortens its shorter side, and its taller side still sets its height. Here 60 still had height $2$ after 65 was gone. The repair can then take a level off, so the subtree comes out one level shorter than before the removal. A subtree that comes out shorter changes the balance factor of its parent, and the parent may become unbalanced in turn.

A removal can also leave an unbalanced node with a heavy child whose balance factor is $0$, which an insertion never does. There is no bend then, so it counts as the same-direction case, and a single rotation fixes it.

So after a removal, a repair does not mean you can stop. Keep following the path up and check every node on the path to the root.