Rebalancing After Deletion
You'll learn how deletion in an AVL tree can trigger multiple rebalancing steps up toward the root, unlike insertion which stops after one rotation.
The Cascading Challenge
When you delete a node from an AVL tree, you might create an imbalance at the parent of the deleted node. Here's the tricky part: fixing that imbalance can reduce the height of that subtree, which may then trigger an imbalance at the parent's parent, and so on up the tree.
This is different from insertion, where a single rotation always fixes the problem and you're done.
Why It Cascades
Think of a tower of blocks. When you remove a block (deletion), the tower might tilt at that spot. You straighten it out, but now your "fixed" section is shorter than before. This shorter height might make the next level up unbalanced, requiring another fix. You might need to straighten multiple levels all the way to the top.
The Algorithm Pattern
After deleting a node:
- Start at the parent of the physically removed node
- Move up toward the root, updating each ancestor's balance factor
- At each ancestor, check if it's now imbalanced (balance factor > 1 or < -1)
- If imbalanced, apply the appropriate rotation (right, left, left-right, or right-left)
- Keep going up — don't stop after one rotation
- Continue until you reach the root
The key difference: you must check every ancestor on the path back to the root, not just the first imbalanced node.
Key Takeaway: Deletion in AVL trees requires checking and potentially rebalancing multiple ancestors up to the root, because fixing one imbalance can reduce subtree height and cascade the problem upward.