AVL Tree Definition and Balance Property
What you'll learn: You'll discover what makes an AVL tree "balanced" and how it prevents the worst-case BST scenarios you just learned about.
What Is an AVL Tree?
An AVL tree is a self-balancing binary search tree. It maintains all the BST properties you know (left subtree < node < right subtree), but adds an extra constraint that keeps the tree from becoming lopsided. Named after inventors Adelson-Velsky and Landis (1962), AVL trees were the first self-balancing BST ever invented.
The Balance Property
Here's the magic rule: For every node in an AVL tree, the heights of its left and right subtrees differ by at most 1.
We define the balance factor of a node as:
balance_factor = height(left_subtree) - height(right_subtree)
In a valid AVL tree, every node's balance factor must be -1, 0, or +1.
- Balance factor = 0: perfectly balanced (both subtrees same height)
- Balance factor = +1: left subtree is one level taller
- Balance factor = -1: right subtree is one level taller
If any node has a balance factor of -2, +2, or worse, the tree has violated the AVL property and needs rebalancing.
Why This Matters
Think of it like a mobile hanging from the ceiling—if one side gets too heavy, it tips. The AVL property ensures no branch gets more than one level "heavier" than its sibling, preventing the tree from degenerating into the linked-list shape that gives BSTs their O(n) worst-case.
This constraint guarantees the tree height stays O(log n), ensuring search, insert, and delete all remain O(log n) even in worst-case scenarios.
Key Takeaway: AVL trees enforce a balance factor of -1, 0, or +1 at every node, keeping tree height logarithmic and preventing BST worst-case performance degradation.