Lecture 9 - Deletion of a Node From an AVL Tree

4.3. Deletion of a Node From an AVL Tree

The inverse of the INSERT operation is the DELETE operation: given a value X and an AVL tree T, delete the node containing X and rebalance the resulting tree, if necessary. It turns out that DELETE is considerably more complex than INSERT - we will not go into the details in this course.

To illustrate the additional complexity, recall that to insert a new value into an AVL tree, we never need to do more than 2 rotations in order to restore the tree's balance. We can use rotations to restore the balance when we do a deletion, too, but in some cases we may have to do a rotation at every level of the tree (O(logN) rotations in the worst case).

Here is a tree that causes this worse case # of rotations (we're deleting X). At every node the left subtree is one shorter than the right subtree (numbers shown are height of subtrees):

: Draw the following on the board as you go.

Deleting X upsets the balance at `A'. When we rotate (B up, A down) to fix this, the whole of this subtree - which is E's left subtree - gets shorter. This means the balance at `E' is upset. When we fix this with a rotation (F up, E down) This subtree (D's left subtree) gets shorter - the subtree heights at this stage are 4 on the left and 6 on the right. When we rotate to fix this (D down, M up), we will get a 5-5 balance at D - so now it is one shorter and its parent is out of balance. This can propagate right to the top of the tree.