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:

```495. <PBST item deletion function 495> =
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 496>
<Step 2: Delete PBST node 498>
<Step 3: Finish up after deleting PBST node 503>
}
```

This code is included in 491.

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:

```496. <Step 1: Find PBST node to delete 496> =
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;
if (p == NULL)
return NULL;
}
item = p->pbst_data;
```

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

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:

```497. <Step 1: Find PBST node to delete 496> +=
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:

```498. <Step 2: Delete PBST node 498> =
{     <Case 1 in PBST deletion 499>   }
else   {
{         <Case 2 in PBST deletion 500>       }
else       {         <Case 3 in PBST deletion 501>       }
}
```

This code is included in 495.

##### 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.

```499. <Case 1 in PBST deletion 499> =
```

This code is included in 498, 538, and 570.

##### 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:

```500. <Case 2 in PBST deletion 500> =
r->pbst_parent = p->pbst_parent;
```

This code is included in 498, 539, and 571.

##### 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:

```501. <Case 3 in PBST deletion 501> =
r = s->pbst_parent;
```

This code is included in 498, 540, and 572.

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:

```502. <Case 3 in PBST deletion 501> +=
s->pbst_parent = p->pbst_parent;
```

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

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

This code is included in 495.