The AVL Property

A node is balanced when its balance factor is $-1$, $0$, or $1$:

$$|\text{bf}(node)|\le 1$$

A node with a balance factor of $2$ or $-2$, like the roots of the two chains we used to define the balance factor, is not balanced.

But a single balanced node is not enough to make a tree balanced. Think back to the ordering property of a binary search tree. It had to hold at every node, not only at the root. Balance is the same kind of rule: if any node at any depth is not balanced, the tree is not balanced.

In this tree, every node passes the check:

       ╭───╮
       │ 5 │
       ╰─┬─╯
    ┌────┴─────┐
  ╭─┴─╮      ╭─┴─╮
  │ 3 │      │ 7 │
  ╰───╯      ╰─┬─╯
               └─┐
               ╭─┴─╮
               │ 9 │
               ╰───╯

The root 5 is right-heavy, with $\text{bf}=-1$, which is allowed.

A binary search tree that keeps every node balanced is an AVL tree, named after its inventors, Adelson-Velskii and Landis. It holds two properties at once: the ordering property from the last chapter, and the balance property we just stated.

This combined property is the invariant of an AVL tree. Every insertion and every removal must leave it true. Keeping every node balanced is what keeps the whole tree short, so its height stays about $\log n$ and it does not turn into a degenerate chain. We will see why at the end of the chapter.