Course contentsShow
← Computer Science
Lesson 542 of 2,87213. Balanced TreesFree lesson

Rebalancing After Deletion

Apply rotations at multiple ancestors when deletion creates cascading imbalances up the tree.

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:

  1. Start at the parent of the physically removed node
  2. Move up toward the root, updating each ancestor's balance factor
  3. At each ancestor, check if it's now imbalanced (balance factor > 1 or < -1)
  4. If imbalanced, apply the appropriate rotation (right, left, left-right, or right-left)
  5. Keep going up — don't stop after one rotation
  6. 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.