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:


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:


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);
return (void *) item;
This code is included in @refalso{493

See also: [ Cormen 1990], section 13.3.


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