Balance and the AVL Property

The height of a node is the number of edges on the longest path from it down to a leaf, and an empty subtree has height $- 1$ . The balance factor of a node is the height of its left subtree minus the height of its right subtree.

Exercise

Give the balance factor of every node in this binary search tree. Is it an AVL tree?

                          ╭────╮
                          │ 50 │
                          ╰──┬─╯
             ┌───────────────┴───────────────┐
          ╭──┴─╮                          ╭──┴─╮
          │ 30 │                          │ 70 │
          ╰──┬─╯                          ╰──┬─╯
       ┌─────┴─────┐                   ┌─────┴─────┐
    ╭──┴─╮      ╭──┴─╮              ╭──┴─╮      ╭──┴─╮
    │ 20 │      │ 40 │              │ 60 │      │ 80 │
    ╰──┬─╯      ╰──┬─╯              ╰──┬─╯      ╰──┬─╯
   ┌───┘       ┌───┴───┐           ┌───┘       ┌───┴───┐
╭──┴─╮      ╭──┴─╮  ╭──┴─╮      ╭──┴─╮      ╭──┴─╮  ╭──┴─╮
│ 10 │      │ 35 │  │ 45 │      │ 55 │      │ 75 │  │ 85 │
╰────╯      ╰────╯  ╰────╯      ╰──┬─╯      ╰────╯  ╰──┬─╯
                               ┌───┘                   └───┐
                            ╭──┴─╮                      ╭──┴─╮
                            │ 52 │                      │ 90 │
                            ╰────╯                      ╰────╯

Solution

10, 35, 45, 52, 75, and 90 are leaves, so each has a balance factor of $0$ . For the other nodes, 20 is $1$ , 30 is $0$ , 40 is $0$ , 55 is $1$ , 60 is $2$ , 70 is $0$ , 85 is $- 1$ , 80 is $- 1$ , and 50 is $- 1$ .

It is not an AVL tree. 60 has a balance factor of $2$ , and an AVL tree needs every node’s balance factor to be $- 1$ , $0$ , or $1$ . The root being balanced is not enough.

Solution

If only the root had to be balanced, each of its two subtrees could be a long chain. With $n$ nodes, the tree could then have height about $n /2$ , and search would be $O (n)$ . The $O (lo g n)$ height bound holds only when every node is balanced.