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(structpbst_table*tree,constvoid*item)

{structpbst_node*p; /* Traverses tree to find node to delete. */structpbst_node*q; /* Parent ofp. */intdir; /* Side ofqon whichpis 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)returnNULL;p=tree->pbst_root;for(;;)

{intcmp=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)returnNULL; }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= (structpbst_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

{structpbst_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.

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.

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.

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> =structpbst_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]