www.delorie.com/gnu/docs/avl/libavl_231.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

14.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:

 
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); &#60;@xref{\NODE\, , Step 1: Find PBST node to delete.&#62;,494} &#60;@xref{\NODE\, , Step 2: Delete PBST node.&#62;,496} &#60;@xref{\NODE\, , Step 3: Finish up after deleting PBST node.&#62;,501} }
This code is included in @refalso{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:

 
if (tree-&#62;pbst_root == NULL)
  return NULL;
p = tree-&#62;pbst_root;
for (;;) 
{ int cmp = tree-&#62;pbst_compare (item, p-&#62;pbst_data, tree-&#62;pbst_param); if (cmp == 0) break; dir = cmp > 0; p = p-&#62;pbst_link[dir]; if (p == NULL) return NULL; } item = p-&#62;pbst_data;
See also @refalso{495 This code is included in @refalso{493

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:

 
q = p-&#62;pbst_parent;
if (q == NULL) 
{ q = (struct pbst_node *) &tree-&#62;pbst_root; dir = 0; }

The remainder of the deletion follows the usual outline:

 
if (p-&#62;pbst_link[1] == NULL)
  { 
&#60;@xref{\NODE\, , Case 1 in PBST deletion.&#62;,497}
} else
{ struct pbst_node *r = p-&#62;pbst_link[1]; if (r-&#62;pbst_link[0] == NULL) {
&#60;@xref{\NODE\, , Case 2 in PBST deletion.&#62;,498}
} else
{
&#60;@xref{\NODE\, , Case 3 in PBST deletion.&#62;,499}
} }
This code is included in @refalso{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.

 
q-&#62;pbst_link[dir] = p-&#62;pbst_link[0];
if (q-&#62;pbst_link[dir] != NULL)
  q-&#62;pbst_link[dir]-&#62;pbst_parent = p-&#62;pbst_parent;
This code is included in @refalso{496

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:

pbstdel1

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:

 
r-&#62;pbst_link[0] = p-&#62;pbst_link[0];
q-&#62;pbst_link[dir] = r;
r-&#62;pbst_parent = p-&#62;pbst_parent;
if (r-&#62;pbst_link[0] != NULL)
  r-&#62;pbst_link[0]-&#62;pbst_parent = r;
This code is included in @refalso{496

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:

 
struct pbst_node *s = r-&#62;pbst_link[0];
while (s-&#62;pbst_link[0] != NULL)
  s = s-&#62;pbst_link[0];
r = s-&#62;pbst_parent;
See also @refalso{500 This code is included in @refalso{496

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:

pbstdel2

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:

 
r-&#62;pbst_link[0] = s-&#62;pbst_link[1];
s-&#62;pbst_link[0] = p-&#62;pbst_link[0];
s-&#62;pbst_link[1] = p-&#62;pbst_link[1];
q-&#62;pbst_link[dir] = s;
if (s-&#62;pbst_link[0] != NULL)
  s-&#62;pbst_link[0]-&#62;pbst_parent = s;
s-&#62;pbst_link[1]-&#62;pbst_parent = s;
s-&#62;pbst_parent = p-&#62;pbst_parent;
if (r-&#62;pbst_link[0] != NULL)
  r-&#62;pbst_link[0]-&#62;pbst_parent = r;

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

 
tree-&#62;pbst_alloc-&#62;libavl_free (tree-&#62;pbst_alloc, p);
tree-&#62;pbst_count--;
return (void *) item;
This code is included in @refalso{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-&#62;pbst_parent to q? [answer]


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003