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


GNU libavl 2.0.1

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

8.7 Deletion

When we delete a node from a threaded tree, we have to update one or two more pointers than if it were an unthreaded BST. What's more, we sometimes have to go to a bit of effort to track down what pointers these are, because they are in the predecessor and successor of the node being deleted.

The outline is the same as for deleting a BST node:

 
void *
tbst_delete (struct tbst_table *tree, const void *item)
{ struct tbst_node *p; /* Node to delete. */ struct tbst_node *q; /* Parent of p. */ int dir; /* Index into q-&#62;tbst_link[] that leads to p. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Find TBST node to delete.&#62;,258} &#60;@xref{\NODE\, , Delete TBST node.&#62;,259} &#60;@xref{\NODE\, , Finish up after deleting TBST node.&#62;,266} }
This code is included in @refalso{251

We search down the tree to find the item to delete, p. As we do it we keep track of its parent q and the direction dir that we descended from it. The initial value of q and dir use the trick seen originally in copying a BST (see section 5.10.2 Iterative Copying).

There are nicer ways to do the same thing, though they are not necessarily as efficient. See the exercises for one possibility.

 
if (tree-&#62;tbst_root == NULL)
  return NULL;
p = tree-&#62;tbst_root;
q = (struct tbst_node *) &tree-&#62;tbst_root;
dir = 0;
for (;;) 
{ int cmp = tree-&#62;tbst_compare (item, p-&#62;tbst_data, tree-&#62;tbst_param); if (cmp == 0) break; dir = cmp > 0; if (p-&#62;tbst_tag[dir] == TBST_THREAD) return NULL; q = p; p = p-&#62;tbst_link[dir]; } item = p-&#62;tbst_data;
This code is included in @refalso{257

The cases for deletion from a threaded tree are a bit different from those for an unthreaded tree. The key point to keep in mind is that a node with n children has n threads pointing to it that must be updated when it is deleted. Let's look at the cases in detail now.

Here's the outline:

 
if (p-&#62;tbst_tag[1] == TBST_THREAD) 
{ if (p-&#62;tbst_tag[0] == TBST_CHILD) {
&#60;@xref{\NODE\, , Case 1 in TBST deletion.&#62;,260}
} else
{
&#60;@xref{\NODE\, , Case 2 in TBST deletion.&#62;,261}
} }
else
{ struct tbst_node *r = p-&#62;tbst_link[1]; if (r-&#62;tbst_tag[0] == TBST_THREAD) {
&#60;@xref{\NODE\, , Case 3 in TBST deletion.&#62;,262}
} else
{
&#60;@xref{\NODE\, , Case 4 in TBST deletion.&#62;,263}
} }
This code is included in @refalso{257

Case 1: p has a right thread and a left child

If p has a right thread and a left child, then we replace it by its left child. We also replace its predecessor t's right thread by p's right thread. In the most general subcase, the whole operation looks something like this:

tbstdel1

On the other hand, it can be as simple as this:

tbstdel1triv

Both of these subcases, and subcases in between them in complication, are handled by the same code:

 
struct tbst_node *t = p-&#62;tbst_link[0];
while (t-&#62;tbst_tag[1] == TBST_CHILD)
  t = t-&#62;tbst_link[1];
t-&#62;tbst_link[1] = p-&#62;tbst_link[1];
q-&#62;tbst_link[dir] = p-&#62;tbst_link[0];
This code is included in @refalso{259

Case 2: p has a right thread and a left thread

If p is a leaf, then no threads point to it, but we must change its parent q's pointer to p to a thread, pointing to the same place that the corresponding thread of p pointed. This is easy, and typically looks something like this:

tbstdel2

There is one special case, which comes up when q is the pseudo-node used for the parent of the root. We can't access tbst_tag[] in this "node". Here's the code:

 
q-&#62;tbst_link[dir] = p-&#62;tbst_link[dir];
if (q != (struct tbst_node *) &tree-&#62;tbst_root)
  q-&#62;tbst_tag[dir] = TBST_THREAD;
This code is included in @refalso{259

Case 3: p's right child has a left thread

If p has a right child r, and r itself has a left thread, then we delete p by moving r into its place. Here's an example where the root node is deleted:

tbstdel3

This just involves changing q's right link to point to r, copying p's left link and tag into r, and fixing any thread that pointed to p so that it now points to r. The code is straightforward:

 
r-&#62;tbst_link[0] = p-&#62;tbst_link[0];
r-&#62;tbst_tag[0] = p-&#62;tbst_tag[0];
if (r-&#62;tbst_tag[0] == TBST_CHILD) 
{ struct tbst_node *t = r-&#62;tbst_link[0]; while (t-&#62;tbst_tag[1] == TBST_CHILD) t = t-&#62;tbst_link[1]; t-&#62;tbst_link[1] = r; } q-&#62;tbst_link[dir] = r;
This code is included in @refalso{259

Case 4: p's right child has a left child

If p has a right child, which in turn has a left child, we arrive at the most complicated case. It corresponds to case 3 in deletion from an unthreaded BST. The solution is to find p's successor s and move it in place of p. In this case, r is s's parent node, not necessarily p's right child.

There are two subcases here. In the first, s has a right child. In that subcase, s's own successor's left thread already points to s, so we need not adjust any threads. Here's an example of this subcase. Notice how the left thread of node 3, s's successor, already points to s.

tbstdel4

The second subcase comes up when s has a right thread. Because s also has a left thread, this means that s is a leaf. This subcase requires us to change r's left link to a thread to its predecessor, which is now s. Here's a continuation of the previous example, showing deletion of the new root, node 2:

tbstdel4-2

The first part of the code handles finding r and s:

 
struct tbst_node *s;
for (;;) 
{ s = r-&#62;tbst_link[0]; if (s-&#62;tbst_tag[0] == TBST_THREAD) break; r = s; }
See also @refalso{264 This code is included in @refalso{259

Next, we update r, handling each of the subcases:

 
if (s-&#62;tbst_tag[1] == TBST_CHILD)
  r-&#62;tbst_link[0] = s-&#62;tbst_link[1];
else 
{ r-&#62;tbst_link[0] = s; r-&#62;tbst_tag[0] = TBST_THREAD; }

Finally, we copy p's links and tags into s and chase down and update any right thread in s's left subtree, then replace the pointer from q down to s:

 
s-&#62;tbst_link[0] = p-&#62;tbst_link[0];
if (p-&#62;tbst_tag[0] == TBST_CHILD) 
{ struct tbst_node *t = p-&#62;tbst_link[0]; while (t-&#62;tbst_tag[1] == TBST_CHILD) t = t-&#62;tbst_link[1]; t-&#62;tbst_link[1] = s; s-&#62;tbst_tag[0] = TBST_CHILD; } s-&#62;tbst_link[1] = p-&#62;tbst_link[1]; s-&#62;tbst_tag[1] = TBST_CHILD; q-&#62;tbst_link[dir] = s;

We finish up by deallocating the node, decrementing the tree's item count, and returning the deleted item's data:

 
tree-&#62;tbst_alloc-&#62;libavl_free (tree-&#62;tbst_alloc, p);
tree-&#62;tbst_count--;
return (void *) item;
This code is included in @refalso{257

Exercises:

*1. In a threaded BST, there is an efficient algorithm to find the parent of a given node. Use this algorithm to reimplement &#60;@xref{\NODE\, , \TITLE\}.&#62;{Find TBST node to delete,258}. [answer]

2. In case 2, we must handle q as the pseudo-root as a special case. Can we rearrange the TBST data structures to avoid this? [answer]

3. Rewrite case 4 to replace the deleted node's tbst_data by its successor and actually delete the successor, instead of moving around pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]

*4. Many of the cases in deletion from a TBST require searching down the tree for the nodes with threads to the deleted node. Show that this adds only a constant number of operations to the deletion of a randomly selected node, compared to a similar deletion in an unthreaded tree. [answer]


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

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