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


GNU libavl 2.0.1

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

5.8 Deletion

Deleting an item from a binary search tree is a little harder than inserting one. Before we write any code, let's consider how to delete nodes from a binary search tree in an abstract fashion. Here's a BST from which we can draw examples during the discussion:

bstdel

It is more difficult to remove some nodes from this tree than to remove others. Here, we recognize three distinct cases (Exercise 4.8-1 offers a fourth), described in detail below in terms of the deletion of a node designated p.

Case 1: p has no right child

It is trivial to delete a node with no right child, such as node 1, 4, 7, or 8 above. We replace the pointer leading to p by p's left child, if it has one, or by a null pointer, if not. In other words, we replace the deleted node by its left child. For example, the process of deleting node 8 looks like this:

bstdel2

This diagram shows the convention of separating multiple labels on a single node by a comma: node 8 is also node p.

Case 2: p's right child has no left child

This case deletes any node p with a right child r that itself has no left child. Nodes 2, 3, and 6 in the tree above are examples. In this case, we move r into p's place, attaching p's former left subtree, if any, as the new left subtree of r. For instance, to delete node 2 in the tree above, we can replace it by its right child 3, giving node 2's left child 1 to node 3 as its new left child. The process looks like this:

bstdel3

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

This is the "hard" case, where p's right child r has a left child. but if we approach it properly we can make it make sense. Let p's inorder successor (see inorder successor), that is, the node with the smallest value greater than p, be s. Then, our strategy is to detach s from its position in the tree, which is always an easy thing to do, and put it into the spot formerly occupied by p, which disappears from the tree. In our example, to delete node 5, we move inorder successor node 6 into its place, like this:

bstdel4

But how do we know that node s exists and that we can delete it easily? We know that it exists because otherwise this would be case 1 or case 2 (consider their conditions). We can easily detach from its position for a more subtle reason: s is the inorder successor of p and is therefore has the smallest value in p's right subtree, so s cannot have a left child. (If it did, then this left child would have a smaller value than s, so it, rather than s, would be p's inorder successor.) Because s doesn't have a left child, we can simply replace it by its right child, if any. This is the mirror image of case 1.

Implementation

The code for BST deletion closely follows the above discussion. Let's start with an outline of the function:

 
void *
bst_delete (struct bst_table *tree, const void *item)
{ struct bst_node *p, *q; /* Node to delete and its parent. */ int cmp; /* Comparison between p-&#62;bst_data and item. */ int dir; /* Side of q on which p is located. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Find BST node to delete.&#62;,38} &#60;@xref{\NODE\, , Step 2: Delete BST node.&#62;,39} &#60;@xref{\NODE\, , Step 3: Finish up after deleting BST node.&#62;,44} }
This code is included in @refalso{29

We begin by finding the node to delete, in much the same way that bst_find() did. But, in every case above, we replace the link leading to the node being deleted by another node or a null pointer. To do so, we have to keep track of the pointer that led to the node to be deleted. This is the purpose of q and dir in the code below.

 
p = (struct bst_node *) &tree-&#62;bst_root;
for (cmp = -1; cmp != 0; 
cmp = tree-&#62;bst_compare (item, p-&#62;bst_data, tree-&#62;bst_param))
{ dir = cmp > 0; q = p; p = p-&#62;bst_link[dir]; if (p == NULL) return NULL; } item = p-&#62;bst_data;
This code is included in @refalso{37

Now we can actually delete the node. Here is the code to distinguish between the three cases:

 
if (p-&#62;bst_link[1] == NULL) { &#60;@xref{\NODE\, , Case 1 in BST deletion.&#62;,40} }
else 
{ struct bst_node *r = p-&#62;bst_link[1]; if (r-&#62;bst_link[0] == NULL)
{ &#60;@xref{\NODE\, , Case 2 in BST deletion.&#62;,41} }
else
{ &#60;@xref{\NODE\, , Case 3 in BST deletion.&#62;,42} } }
This code is included in @refalso{37

In case 1, we simply replace the node by its left subtree:

 
q-&#62;bst_link[dir] = p-&#62;bst_link[0];
This code is included in @refalso{39

In case 2, we attach the node's left subtree as its right child r's left subtree, then replace the node by r:

 
r-&#62;bst_link[0] = p-&#62;bst_link[0];
q-&#62;bst_link[dir] = r;
This code is included in @refalso{39

We begin case 3 by finding p's inorder successor as s, and the parent of s as r. Node p's inorder successor is the smallest value in p's right subtree and that the smallest value in a tree can be found by descending to the left until a node with no left child is found:

 
struct bst_node *s;
for (;;) 
{ s = r-&#62;bst_link[0]; if (s-&#62;bst_link[0] == NULL) break; r = s; }
See also @refalso{43 This code is included in @refalso{39

Case 3 wraps up by adjusting pointers so that s moves into p's place:

 
r-&#62;bst_link[0] = s-&#62;bst_link[1];
s-&#62;bst_link[0] = p-&#62;bst_link[0];
s-&#62;bst_link[1] = p-&#62;bst_link[1];
q-&#62;bst_link[dir] = s;

As the final step, we decrement the number of nodes in the tree, free the node, and return its data:

 
tree-&#62;bst_alloc-&#62;libavl_free (tree-&#62;bst_alloc, p);
tree-&#62;bst_count--;
tree-&#62;bst_generation++;
return (void *) item;
This code is included in @refalso{37

See also: [ Knuth 1998b], algorithm 6.2.2D; [ Cormen 1990], section 13.3.

Exercises:

1. Write code for a case 1.5 which handles deletion of nodes with no left child. [answer]

2. In the code presented above for case 3, we update pointers to move s into p's position, then free p. An alternate approach is to replace p's data by s's and delete s. Write code to use this approach. Can a similar modification be made to either of the other cases? [answer]

*3. The code in the previous exercise is a few lines shorter than that in the main text, so it would seem to be preferable. Explain why the revised code, and other code based on the same idea, cannot be used in libavl. (Hint: consider the semantics of libavl traversers.) [answer]

5.8.1 Aside: Deletion by Merging  


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

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