www.delorie.com/gnu/docs/avl/libavl_231.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The new aspect of deletion in a PBST is that we must properly adjust parent pointers. The outline is the same as usual:
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->pbst_root == NULL) return NULL; p = tree->pbst_root; for (;;) |
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->pbst_parent; if (q == NULL) |
The remainder of the deletion follows the usual outline:
if (p->pbst_link[1] == NULL) { |
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->pbst_link[dir] = p->pbst_link[0]; if (q->pbst_link[dir] != NULL) q->pbst_link[dir]->pbst_parent = p->pbst_parent; |
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->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; |
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->pbst_link[0]; while (s->pbst_link[0] != NULL) s = s->pbst_link[0]; r = s->pbst_parent; |
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->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:
tree->pbst_alloc->libavl_free (tree->pbst_alloc, p); tree->pbst_count--; return (void *) item; |
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]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |