When a binary search tree grows mostly to one side, searching can become slow. An AVL tree keeps its height controlled by balancing itself, so it remains useful when ordinary trees lose their advantage. section 8.0 section 8.4
An AVL tree maintains its shape through three connected ideas:
- It is a binary search tree that maintains height O(log n), rather than allowing one side to grow excessively. section 8.4
- Each node stores either its height or its balance factor; the balance factor may be −1, 0, or 1 when the node is acceptably balanced. section 8.6
- After an insertion, the tree updates heights and balance factors along the node’s ancestors. section 8.6
- When a balance factor falls below −1 or rises above 1, the tree uses a rotation to restore balance. section 8.5 section 8.6
Balancing after an insertion
Imagine adding nodes one at a time. A small height difference of 1 is acceptable, but another insertion can push a node’s balance factor to −2. The AVL tree then rotates the affected subtree; in one walkthrough, a left rotation changes A from the root to B, producing a balanced arrangement. Later insertions trigger further rotations, including one involving node 30 rather than node 20. section 8.5 section 8.6
Follow the staged tree figures to see how an insertion creates imbalance and how rotation rearranges the nodes. section 8.5
