Height-Balance Invariant
You'll learn how AVL trees keep operations fast by enforcing a strict balance rule on every node.
The Core Idea
In an AVL tree, every single node must satisfy the height-balance invariant: the heights of its left and right subtrees can differ by at most one. This simple rule prevents the tree from becoming lopsided like a worst-case BST (which degenerates into a linked list).
Remember from earlier lessons that BST operations depend on tree height. A balanced tree with n nodes has height O(log n), while an unbalanced one can degrade to O(n). By enforcing the height-balance invariant at every node, AVL trees guarantee their height never exceeds approximately 1.44 × log₂(n), keeping all operations—search, insertion, deletion—solidly in O(log n) territory.
How It Works
Think of the invariant as a "wobble limit." Each node can lean slightly left or right, but never too far:
- Balance Factor = height(left subtree) − height(right subtree)
- Valid range: -1, 0, or +1
- If balance factor becomes -2 or +2, the tree violates the invariant and must be rebalanced (through rotations, which we'll cover later)
This per-node enforcement ensures the entire tree stays logarithmically shallow. Even if you insert nodes in sorted order—the nightmare scenario for regular BSTs—an AVL tree will maintain balance through automatic adjustments.
Why It Matters
Without this invariant, a BST with 1,000 nodes could have height 1,000 (terrible) or height 10 (excellent). The height-balance invariant guarantees the excellent case, making AVL trees predictable and reliable for performance-critical applications.
Key Takeaway: The height-balance invariant ensures every node's subtrees differ in height by at most one, locking AVL tree height at O(log n) and guaranteeing fast operations regardless of insertion order.