5.5 Deletion

Deletion in an AVL tree is remarkably similar to insertion. The steps that we go through are analogous:

1. Search for the item to delete.
2. Delete the item.
3. Update balance factors.
4. Rebalance the tree, if necessary.
5. Finish up and return.

The main difference is that, after a deletion, we may have to rebalance at more than one level of a tree, starting from the bottom up. This is a bit painful, because it means that we have to keep track of all the nodes that we visit as we search for the node to delete, so that we can then move back up the tree. The actual updating of balance factors and rebalancing steps are similar to those used for insertion.

The following sections cover deletion from an AVL tree in detail. Before we get started, here's an outline of the function.

164. <AVL item deletion function 164> =
void *
avl_delete (struct avl_table *tree, const void *item) 
{
  /* Stack of nodes. */
struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */
unsigned char da[AVL_MAX_HEIGHT];    /* avl_link[] indexes. */
int k;                               /* Stack pointer. */
struct avl_node *p;   /* Traverses tree to find node to delete. */
int cmp;              /* Result of comparison between item and p. */
assert (tree != NULL && item != NULL);
<Step 1: Search AVL tree for item to delete 165>
<Step 2: Delete item from AVL tree 166>
<Steps 3–4: Update balance factors and rebalance after AVL deletion 171>
<Step 5: Finish up and return after AVL deletion 176>
}

This code is included in 145.

See also: [Knuth 1998b], pages 473–474; [Pfaff 1998].

• Deleting an AVL Node Step 1 - Search
• Deleting an AVL Node Step 2 - Delete
• Deleting an AVL Node Step 3 - Update
• Deleting an AVL Node Step 4 - Rebalance
• Deleting an AVL Node Step 5 - Finish Up
• AVL Deletion Symmetric Case