Deleting from a PRB Tree - GNU libavl 2.0.3

15.4 Deletion

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.

568. <PRB item deletion function 568> =
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 496>
  <Step 2: Delete item from PRB tree 569>
  <Step 3: Rebalance tree after PRB deletion 573>
  <Step 4: Finish up after PRB deletion 579>
}

This code is included in 556.

See also: [Cormen 1990], section 14.4.