AVL trees: deletion

Deleting from an AVL tree

This builds on AVL insertion: the same rule (every balance factor is −1, 0 or +1), the same four rotation cases and the same names A, B, C. Deletion has two parts:

1. Remove the key as in a plain binary search tree. A leaf just goes; a node with one child is replaced by that child; a node with two children is replaced by its in-order successor (right once, then left as far as possible).
2. Walk back up from where a node was actually removed (the deleted node's parent, or the successor's old parent), updating heights and checking each balance factor.

Same checks, opposite conclusions

After a deletion, a subtree can only get shorter. That flips what each balance factor means:

Balance factor now	After an insertion	After a deletion
0	Height unchanged: stop	The taller side shrank, so the node got shorter: keep walking up
+1 or −1	The node grew: keep walking up	It was 0 before, so its height is unchanged: stop
+2 or −2	Rotate, then stop	Rotate, then keep walking up if the subtree got shorter

A new situation: B is balanced

After an insertion, the taller child B is always leaning one way. After a deletion, B can be perfectly balanced (0). That counts as a straight line: a single rotation fixes it, and because both of B's subtrees were equally tall, the rotated subtree keeps its old height, so the walk stops.

Possibly many rotations

An insertion needs at most one rebalancing, because the rotation restores the subtree's old height. After a deletion, a rotation usually leaves the subtree one level shorter, which can unbalance the next ancestor up, and so on. In the worst case there is a rotation at every level, O(log n) of them, still cheap enough that deletion stays O(log n).

Start the walkthrough →