5.7 Deletion for an AVL tree

Deleting a node in an AVL tree is slightly different. This is because an AVL tree guarantees that the maximum link difference between any leaf and the root is 1. This means that, in the worst case, the node to replace the node being deleted is at the most one above a leaf.

As a result, there are only a few cases to handle. Let us consider the deletion of node n, and the tree rooted at n is as (T_L,n,T_R).

• T_L and T_R are both empty. In this case, node n can be deleted safely. The tree pointed to n should be updated.
• h(T_L) ≥ h(T_R): because the left tree has a taller height, we attempt to use a node from T_L to replace n.
  • Find the right most descendent m. m is either a leaf, or it has a single left child.
  • If m has a single left child l, update v(n) = v(m), then update v(m) = v(l), then delete node l.
  • If m is a leaf, update v(n) = v(m), then delete node m.
• h(T_L) < h(T_R): we use a node from T_R to replace n.
  • Find the left most descendent m. m is either a leaf, or it has a single right child.
  • If m has a single right child r, update v(n) = v(m), then update v(m) = v(l), then delete node r.
  • If m is a leaf, update v(n) = v(m), then delete n.