AVL Idea: Balance Factor

An AVL tree is a binary search tree in which the heights of the child subtrees differ by at most 1. The balance factor of a node is defined as height(left) - height(right) (or vice versa; consistency is key).

After insertion or deletion, the invariant may be broken. Rotations locally restore it.

Goal: Height remains $\Theta(\log n)$.

$$|h_L - h_R| \le 1$$

Where used

Teaching framework for self-balancing trees. In practice, often Red-Black trees (TreeMap) or B-trees; the balance invariant is the same product idea: maintain height in $O(\log n)$.

Depth

An AVL tree adds a local height condition to the search order. The balance factor of a node is the difference in heights between its two subtrees. Only small deviations are allowed.

After a modification, heights can change along the path to the root. Other subtrees remain unchanged. Therefore, it is sufficient to check this path backward and repair the first or further affected nodes.

The local condition limits the global height. The smallest AVL tree of a given height recursively contains a minimal tree of the two previous heights, resulting in a Fibonacci-like size sequence.

Difficulty levels

1. Calculate balance factors from subtree heights.
2. Determine affected ancestors after a modification.
3. Justify a logarithmic height from the minimal size recurrence.

Pitfalls

Sign conventions for the balance factor differ. Consistent usage is crucial; no rotation direction should be inferred from a sign alone without definition.