AVL Deletion Overview
You'll learn: How to remove a node from an AVL tree while maintaining its strict height-balance property.
Deleting from an AVL tree is a two-phase operation. First, you perform a standard BST deletion (handling leaf, one-child, or two-children cases just like you learned). Second—and this is what makes it an AVL deletion—you travel back up the path from the deletion point to the root, checking and fixing any balance violations along the way.
Why Deletion Can Cause Imbalance
When you remove a node, you effectively shorten one branch of the tree. This can cause ancestor nodes to become unbalanced (balance factor becomes -2 or +2). Unlike insertion, where at most one rotation fixes the tree, deletion may require rotations at multiple levels as you walk back up to the root.
The Process
- Delete normally: Use BST deletion rules (remove leaf, bypass single-child node, or replace with inorder successor/predecessor)
- Walk upward: Starting from the parent of the deleted node, move toward the root
- Update heights: Recalculate each ancestor's height using its children
- Check balance: Compute the balance factor at each node
- Rotate if needed: If imbalanced, determine the rotation type (single right, single left, left-right, or right-left) based on the heavier subtree
- Continue upward: Keep checking and rotating until you reach the root
Think of it like Jenga: removing a block might make several levels above it wobbly, not just the one directly above.
Key Takeaway: AVL deletion = BST deletion + rebalancing every ancestor node on the path back to the root, potentially requiring multiple rotations.