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

The RB item deletion algorithm needs the same kind of changes to handle parent pointers that the RB item insertion algorithm did. We can reuse the code from PBST trees for finding the node to delete. The rest of the code will be presented in the following sections. 

566. <PRB item deletion function 566> =
void *
prb_delete (struct prb_table *tree, const void *item) 
{
  struct prb_node *p; /* Node to delete. */
  struct prb_node *q; /* Parent of p. */
  struct prb_node *f; /* Node at which we are rebalancing. */
  int dir;            /* Side of q on which p is a child;
                         side of f from which node was deleted. */

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

  <Step 1: Find PBST node to delete; pbst => prb 494>
  <Step 2: Delete item from PRB tree 567>
  <Step 3: Rebalance tree after PRB deletion 571>
  <Step 4: Finish up after PRB deletion 577>
}

This code is included in 554.

See also:  [Cormen 1990], section 14.4.