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

The process of deletion from an RB tree is very much in line with the other algorithms for balanced trees that we've looked at already. This time, the steps are:

  1. Search for the item to delete.
  2. Delete the item.
  3. Rebalance the tree as necessary.
  4. Finish up and return.

Here's an outline of the code. Step 1 is already done for us, because we can reuse the search code from AVL deletion. 

220. <RB item deletion function 220> =
void *
rb_delete (struct rb_table *tree, const void *item) 
{
  struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */
  unsigned char da[RB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
  int k;                             /* Stack height. */

  struct rb_node *p;    /* The node to delete, or a node part way to it. */
  int cmp;              /* Result of comparison between item and p. */

  assert (tree != NULL && item != NULL);

  <Step 1: Search AVL tree for item to delete; avl => rb 165>
  <Step 2: Delete item from RB tree 221>
  <Step 3: Rebalance tree after RB deletion 225>
  <Step 4: Finish up after RB deletion 232>
}

This code is included in 196.

See also:  [Cormen 1990], section 14.4.