13.4 Deletion

The new aspect of deletion in a PBST is that we must properly adjust parent pointers. The outline is the same as usual:

493. <PBST item deletion function 493> =
void *
pbst_delete (struct pbst_table *tree, const void *item) 
{
  struct pbst_node *p; /* Traverses tree to find node to delete. */
  struct pbst_node *q; /* Parent of p. */
  int dir;             /* Side of q on which p is linked. */

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

  <Step 1: Find PBST node to delete 494>
  <Step 2: Delete PBST node 496>
  <Step 3: Finish up after deleting PBST node 501>
}

This code is included in 489.

We find the node to delete by using p to search for item. For the first time in implementing a deletion routine, we do not keep track of the current node's parent, because we can always find it out later with little effort:

494. <Step 1: Find PBST node to delete 494> =
if (tree->pbst_root == NULL)
  return NULL;

p = tree->pbst_root;
for (;;) 
  {
    int cmp = tree->pbst_compare (item, p->pbst_data, tree->pbst_param);
    if (cmp == 0)
      break;

    dir = cmp > 0;
    p = p->pbst_link[dir];
    if (p == NULL)
      return NULL;
  }
item = p->pbst_data;

See also 495.

Now we've found the node to delete, p. The first step in deletion is to find the parent of p as q. Node p is q's child on side dir. Deletion of the root is a special case:

495. <Step 1: Find PBST node to delete 494> +=
q = p->pbst_parent;
if (q == NULL) 
  {
    q = (struct pbst_node *) &tree->pbst_root;
    dir = 0;
  }

The remainder of the deletion follows the usual outline:

496. <Step 2: Delete PBST node 496> =
if (p->pbst_link[1] == NULL)
  { 
    <Case 1 in PBST deletion 497> 
  }
else 
  {
    struct pbst_node *r = p->pbst_link[1];
    if (r->pbst_link[0] == NULL)
      { 
        <Case 2 in PBST deletion 498> 
      }
    else 
      { 
        <Case 3 in PBST deletion 499> 
      }
  }

This code is included in 493.

Case 1: p has no right child

If p has no right child, then we can replace it by its left child, if any. If p does have a left child then we must update its parent to be p's former parent.

497. <Case 1 in PBST deletion 497> =
q->pbst_link[dir] = p->pbst_link[0];
if (q->pbst_link[dir] != NULL)
  q->pbst_link[dir]->pbst_parent = p->pbst_parent;

This code is included in 496, 536, and 568.

Case 2: p's right child has no left child

When we delete a node with a right child that in turn has no left child, the operation looks like this:

The key points to notice are that node r's parent changes and so does the parent of r's new left child, if there is one. We update these in deletion:

498. <Case 2 in PBST deletion 498> =
r->pbst_link[0] = p->pbst_link[0];
q->pbst_link[dir] = r;
r->pbst_parent = p->pbst_parent;
if (r->pbst_link[0] != NULL)
  r->pbst_link[0]->pbst_parent = r;

This code is included in 496, 537, and 569.

Case 3: p's right child has a left child

If p's right child has a left child, then we replace p by its successor, as usual. Finding the successor s and its parent r is a little simpler than usual, because we can move up the tree so easily. We know that s has a non-null parent so there is no need to handle that special case:

499. <Case 3 in PBST deletion 499> =
struct pbst_node *s = r->pbst_link[0];
while (s->pbst_link[0] != NULL)
  s = s->pbst_link[0];
r = s->pbst_parent;

See also 500.

The only other change here is that we must update parent pointers. It is easy to pick out the ones that must be changed by looking at a diagram of the deletion:

Node s's parent changes, as do the parents of its new right child x and, if it has one, its left child a. Perhaps less obviously, if s originally had a right child, it becomes the new left child of r, so its new parent is r:

500. <Case 3 in PBST deletion 499> +=
r->pbst_link[0] = s->pbst_link[1];
s->pbst_link[0] = p->pbst_link[0];
s->pbst_link[1] = p->pbst_link[1];
q->pbst_link[dir] = s;
if (s->pbst_link[0] != NULL)
  s->pbst_link[0]->pbst_parent = s;
s->pbst_link[1]->pbst_parent = s;
s->pbst_parent = p->pbst_parent;
if (r->pbst_link[0] != NULL)
  r->pbst_link[0]->pbst_parent = r;

Finally, we free the deleted node p and return its data:

501. <Step 3: Finish up after deleting PBST node 501> =
tree->pbst_alloc->libavl_free (tree->pbst_alloc, p);
tree->pbst_count–;
return (void *) item;

This code is included in 493.

See also:  [Cormen 1990], section 13.3.

Exercises:

1. In case 1, can we change the right side of the assignment in the if statement's consequent from p->pbst_parent to q? [answer]