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.

222. <RB item deletion function 222> =
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 167> <Step 2: Delete item from RB tree 223> <Step 3: Rebalance tree after RB deletion 227> <Step 4: Finish up after RB deletion 234> }

This code is included in 198.

See also:  [Cormen 1990], section 14.4.