Loading learning content...
If the AVL tree were a living organism, the balance factor would be its vital sign. Just as a doctor monitors heart rate and blood pressure to detect problems, an AVL tree implementation constantly monitors balance factors to detect—and correct—imbalances before they degrade performance.
In this section, we'll develop a profound understanding of balance factors: how they're computed, how they change during operations, and how violations propagate up the tree. This knowledge is essential for understanding the rotation operations we'll study next.
By the end of this page, you will:
• Master the calculation of balance factors for any node in any tree • Understand how insertions and deletions affect balance factors along the insertion/deletion path • Recognize the four imbalance patterns that require correction • Trace how balance factor changes propagate from modified nodes to the root • Know why detecting and fixing imbalances is always O(log n)
The balance factor of a node is a simple calculation, but getting it right requires careful attention to edge cases. Let's build from first principles.
For any node v in a binary tree:
balanceFactor(v) = height(v.left) - height(v.right)
Where height(null) = -1 by convention.
Why height(null) = -1?
This convention ensures consistent mathematics:
A leaf node (no children) has:
A node with only a left child (which is a leaf):
Let's trace through a complete example, computing every node's balance factor:
Step-by-step calculation (bottom-up):
| Node | Left Height | Right Height | Node Height | Balance Factor | Valid? |
|---|---|---|---|---|---|
| 10 | -1 (null) | -1 (null) | 0 | 0 | ✓ |
| 35 | -1 (null) | -1 (null) | 0 | 0 | ✓ |
| 60 | -1 (null) | -1 (null) | 0 | 0 | ✓ |
| 90 | -1 (null) | -1 (null) | 0 | 0 | ✓ |
| 30 | -1 (null) | 0 (node 35) | 1 | -1 | ✓ |
| 75 | 0 (node 60) | 0 (node 90) | 1 | 0 | ✓ |
| 25 | 0 (node 10) | 1 (node 30) | 2 | -1 | ✓ |
| 50 | 2 (subtree) | 1 (node 75) | 3 | +1 | ✓ |
Every node has balance factor in {-1, 0, +1}, so this is a valid AVL tree.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
def get_height(node): """ Return the height of a node. By convention, null nodes have height -1. This ensures: - Leaf nodes have height 0 - Balance factor calculations work correctly """ if node is None: return -1 return node.height def calculate_balance_factor(node): """ Calculate the balance factor of a node. Balance Factor = height(left subtree) - height(right subtree) Interpretation: - bf > 0: Left-heavy (left subtree is taller) - bf = 0: Perfectly balanced at this node - bf < 0: Right-heavy (right subtree is taller) For a valid AVL tree: bf ∈ {-1, 0, +1} """ if node is None: return 0 # Null nodes are trivially balanced left_height = get_height(node.left) right_height = get_height(node.right) return left_height - right_height def is_balanced(node): """ Check if a single node satisfies the AVL property. Does NOT check descendants - just this node. """ bf = calculate_balance_factor(node) return -1 <= bf <= 1 def is_avl_tree(node): """ Check if the entire subtree rooted at 'node' is a valid AVL tree. Every node must have balance factor in {-1, 0, +1}. """ if node is None: return True # Empty tree is valid # Check this node if not is_balanced(node): return False # Recursively check children return is_avl_tree(node.left) and is_avl_tree(node.right)When we insert a new node into an AVL tree, the balance factors of all its ancestors may change. Understanding this propagation is crucial for knowing when and where to rebalance.
Inserting a node can only increase (or keep equal) the height of subtrees containing it. This height increase propagates upward, potentially changing balance factors all the way to the root.
A subtree's height increases by 1 if and only if the new node is inserted into its taller (or equally tall) side.
Tracing balance factor changes after insertion:
Consider inserting value 5 into this AVL tree:
After inserting 5:
What happened:
The tree is still valid (all bf ∈ {-1, 0, +1}), but both ancestors' balance factors changed.
Height increase stops propagating when it reaches a node where:
In the best case, height propagation stops immediately. In the worst case, it goes all the way to the root.
Example: Insertion that doesn't propagate height changes:
When we inserted 25 under node 30:
Actually, this insertion DOES change node 20's bf from +1 to 0, but height stays at 2. The key point is that height propagation stops, not that bf doesn't change.
When an insertion causes a node's balance factor to become +2 or -2, the tree is no longer a valid AVL tree. There are exactly four distinct imbalance patterns, each requiring a specific type of rotation to fix.
Understanding these four cases is the key to implementing AVL rebalancing.
The four cases are named by the path from the imbalanced node to the newly inserted node:
• Left-Left (LL): Insert into the left subtree of the left child • Left-Right (LR): Insert into the right subtree of the left child • Right-Right (RR): Insert into the right subtree of the right child • Right-Left (RL): Insert into the left subtree of the right child
Left-Left Case: bf = +2, left child has bf ≥ 0
The imbalance is caused by the left subtree being too tall, with the excess height on the left side of the left child.
Pattern recognition:
Fix: Single right rotation at z
Why this works: Rotating right at z moves y up to become the new root. This 'pushes' height from the left side to the right side, restoring balance.
| Case | Parent bf | Child bf | Rotation Type | Direction |
|---|---|---|---|---|
| Left-Left (LL) | +2 | ≥ 0 (left child) | Single | Right at parent |
| Right-Right (RR) | -2 | ≤ 0 (right child) | Single | Left at parent |
| Left-Right (LR) | +2 | < 0 (left child) | Double | Left at child, Right at parent |
| Right-Left (RL) | -2 | 0 (right child) | Double | Right at child, Left at parent |
A critical question in AVL implementation: after inserting a node, how do we find where the imbalance occurred (if at all)?
After an insertion, imbalance (if any) can ONLY occur at nodes on the path from the root to the newly inserted node.
Moreover, only the lowest imbalanced node needs to be fixed—fixing it automatically restores balance to all its ancestors.
Why the lowest imbalanced node is sufficient:
When we fix an imbalanced node through rotation, the height of the subtree rooted at that node either:
In either case, all ancestors see the same or lower height than before, so their balance factors cannot be worse than before the insertion. Since the tree was balanced before insertion, all ancestors remain balanced after we fix the lowest imbalanced node.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
def insert_and_rebalance(root, key): """ Insert a key into an AVL tree and rebalance. Returns the new root of the tree. The algorithm: 1. Perform standard BST insertion 2. Walk back up and update heights 3. Check balance factor at each node 4. If |bf| == 2, perform the appropriate rotation 5. After fixing one imbalance, the tree is balanced """ # Base case: empty tree if root is None: return AVLNode(key) # Step 1: Standard BST insertion if key < root.key: root.left = insert_and_rebalance(root.left, key) elif key > root.key: root.right = insert_and_rebalance(root.right, key) else: return root # Duplicate keys not allowed # Step 2: Update height of current node root.update_height() # Step 3: Check balance factor bf = root.balance_factor() # Step 4: If unbalanced, determine which case # Left-Left Case if bf > 1 and root.left.balance_factor() >= 0: return rotate_right(root) # Right-Right Case if bf < -1 and root.right.balance_factor() <= 0: return rotate_left(root) # Left-Right Case if bf > 1 and root.left.balance_factor() < 0: root.left = rotate_left(root.left) return rotate_right(root) # Right-Left Case if bf < -1 and root.right.balance_factor() > 0: root.right = rotate_right(root.right) return rotate_left(root) # Step 5: Node is balanced, return it return rootNotice how the recursive structure naturally handles bottom-up processing:
This is why AVL insertion is O(log n): at most O(log n) height updates and at most O(1) rotations.
Deletion in AVL trees is more complex than insertion because:
After deletion, we may need up to O(log n) rotations, not just O(1) as with insertion.
Example: Deleting from a 'minimal' AVL tree (one where every node has bf ∈ {-1, +1}) can cause every ancestor to need rebalancing.
How deletion affects balance factors:
When a node is deleted:
If deleted node was in the taller subtree → Subtree height may decrease, bf moves toward 0 or to the opposite sign
If deleted node was in the shorter subtree → Subtree height can't decrease (it was already shorter), bf stays the same
If bf was 0 and we delete from one side → bf becomes ±1, height stays the same
If bf was ±1 and we delete from the taller side → bf becomes 0, height decreases by 1
If bf was ±1 and we delete from the shorter side → bf becomes ±2, rotation needed!
Example of cascading rebalances:
Consider this minimal AVL tree where every node has bf = +1:
If we delete node 30 (the right child of 20):
In a larger tree, this rebalancing might reduce the height of the subtree, causing the parent to become unbalanced, requiring another rotation, and so on up to the root.
Despite potentially needing O(log n) rotations, deletion is still O(log n) overall because:
• Finding the node to delete: O(log n) • Standard BST deletion: O(log n) • Walking back up and rebalancing: O(log n) total • Each rotation is O(1)
The total work is at most 3 passes of O(log n) operations = O(log n).
The balance factor is the diagnostic tool that makes AVL trees work. Let's consolidate our understanding.
What's Next:
Now that we understand balance factors and can identify all four imbalance cases, we're ready to learn the mechanics of rotations — the operations that physically restructure the tree to restore balance. We'll see exactly how single and double rotations work, with step-by-step visualizations and complete code implementations.
You now have a deep understanding of balance factors — how they're computed, how they change during tree modifications, and how they reveal which of the four imbalance patterns has occurred. With this foundation, you're ready to learn the rotation operations that fix these imbalances.