5.5 Deletion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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. 

166. <AVL item deletion function 166> =
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 167>
  <Step 2: Delete item from AVL tree 168>
  <Steps 3–4: Update balance factors and rebalance after AVL deletion 173>
  <Step 5: Finish up and return after AVL deletion 178>
}

This code is included in 147.

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