Insertion and Removal by Hand
Every question on this page uses an AVL tree of integers that starts empty, unless the question gives a starting tree.
Solution
50, 20, 70, 10, and 30 cause no repair. After them, the tree is:
╭────╮
│ 50 │
╰──┬─╯
┌────────┴────────┐
╭──┴─╮ ╭──┴─╮
│ 20 │ │ 70 │
╰──┬─╯ ╰────╯
┌────┴────┐
╭──┴─╮ ╭──┴─╮
│ 10 │ │ 30 │
╰────╯ ╰────╯
Insert 25. It goes to the left of 30. Follow the path back up from 25. 30 has a balance factor of and 20 has , which are allowed. 50 has a balance factor of :
╭────╮
│░50░│ ◀── bf = +2
╰──┬─╯
┌──────────┴──────────┐
╭──┴─╮ ╭──┴─╮
│ 20 │ │ 70 │
╰──┬─╯ ╰────╯
┌───────┴───────┐
╭──┴─╮ ╭──┴─╮
│ 10 │ │ 30 │
╰────╯ ╰──┬─╯
┌───┘
╭──┴─╮
│ 25 │
╰────╯
50 is left-heavy, and its left child 20 is right-heavy. That is a bent shape, so the repair is a left-right double rotation at 50:
╭────╮
│░30░│
╰──┬─╯
┌────────┴────────┐
╭──┴─╮ ╭──┴─╮
│ 20 │ │ 50 │
╰──┬─╯ ╰──┬─╯
┌────┴────┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 10 │ │ 25 │ │ 70 │
╰────╯ ╰────╯ ╰────╯
Insert 80. It goes to the right of 70. 70 has a balance factor of , which is allowed. 50 has a balance factor of :
╭────╮
│ 30 │
╰──┬─╯
┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮
│ 20 │ │░50░│ ◀── bf = -2
╰──┬─╯ ╰──┬─╯
┌────┴────┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 10 │ │ 25 │ │ 70 │
╰────╯ ╰────╯ ╰──┬─╯
└───┐
╭──┴─╮
│ 80 │
╰────╯
50 is right-heavy, and its right child 70 is right-heavy too. That is a straight spine, so the repair is a single left rotation at 50:
╭────╮
│ 30 │
╰──┬─╯
┌──────────┴──────────┐
╭──┴─╮ ╭──┴─╮
│ 20 │ │░70░│
╰──┬─╯ ╰──┬─╯
┌────┴────┐ ┌────┴────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 10 │ │ 25 │ │ 50 │ │ 80 │
╰────╯ ╰────╯ ╰────╯ ╰────╯
Solution
Follow the path back up from where 10 was. The first node is 20. Its left side is now empty, with height , and its right subtree, under 30, has height , so its balance factor is :
╭────╮
│ 50 │
╰──┬─╯
┌───────────┴───────────┐
╭──┴─╮ ╭──┴─╮
bf = -2 ──▶ │░20░│ │ 60 │
╰──┬─╯ ╰──┬─╯
└───┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 55 │ │ 70 │
╰──┬─╯ ╰──┬─╯ ╰──┬─╯
└───┐ └───┐ ┌───┴───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 40 │ │ 58 │ │ 65 │ │ 75 │
╰────╯ ╰────╯ ╰────╯ ╰──┬─╯
└───┐
╭──┴─╮
│ 80 │
╰────╯
20 is right-heavy, and its right child 30 is right-heavy too, so a single left rotation at 20 repairs it. 30 rises, with 20 and 40 as its children:
╭────╮
│ 50 │
╰──┬─╯
┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮
height 1 ──▶ │░30░│ │ 60 │
╰──┬─╯ ╰──┬─╯
┌───┴───┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 20 │ │ 40 │ │ 55 │ │ 70 │
╰────╯ ╰────╯ ╰──┬─╯ ╰──┬─╯
└───┐ ┌───┴───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 58 │ │ 65 │ │ 75 │
╰────╯ ╰────╯ ╰──┬─╯
└───┐
╭──┴─╮
│ 80 │
╰────╯
Before the removal, the subtree at 20 had height . The repaired subtree under 30 has height , one level shorter. Keep following the path up to the root 50. Its left subtree, under 30, has height , and its right subtree, under 60, has height , so 50 has a balance factor of :
╭────╮
│░50░│ ◀── bf = -2
╰──┬─╯
┌─────────┴─────────┐
╭──┴─╮ ╭──┴─╮
│ 30 │ │ 60 │
╰──┬─╯ ╰──┬─╯
┌───┴───┐ ┌───────┴───────┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 20 │ │ 40 │ │ 55 │ │ 70 │
╰────╯ ╰────╯ ╰──┬─╯ ╰──┬─╯
└───┐ ┌───┴───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 58 │ │ 65 │ │ 75 │
╰────╯ ╰────╯ ╰──┬─╯
└───┐
╭──┴─╮
│ 80 │
╰────╯
50 is right-heavy, and its right child 60 is right-heavy too, so a second single left rotation, at 50, repairs it. This is the final tree:
╭────╮
│░60░│
╰──┬─╯
┌──────────┴──────────┐
╭──┴─╮ ╭──┴─╮
│ 50 │ │ 70 │
╰──┬─╯ ╰──┬─╯
┌─────┴─────┐ ┌───┴───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 30 │ │ 55 │ │ 65 │ │ 75 │
╰──┬─╯ ╰──┬─╯ ╰────╯ ╰──┬─╯
┌───┴───┐ └───┐ └───┐
╭──┴─╮ ╭──┴─╮ ╭──┴─╮ ╭──┴─╮
│ 20 │ │ 40 │ │ 58 │ │ 80 │
╰────╯ ╰────╯ ╰────╯ ╰────╯
Solution
An insertion makes a subtree one level taller, and the repair at the lowest unbalanced node brings that subtree back to the height it had before the insertion. The heights of the nodes above it do not change, so none of them can be unbalanced. A removal shortens the shorter side of the unbalanced node, so that node’s subtree still has the height it had before the removal. The repair then takes a level off, so the subtree can come out one level shorter than before. That changes its parent’s balance factor, so the parent can become unbalanced too, and so on up to the root.