www.delorie.com/gnu/docs/avl/libavl_46.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The libavl algorithm for deletion is commonly used, but it is also seemingly ad-hoc and arbitrary in its approach. In this section we'll take a look at another algorithm that may seem a little more uniform. Unfortunately, though it is conceptually simpler in some ways, in practice this algorithm is both slower and more difficult to properly implement.
The idea behind this algorithm is to consider deletion as breaking the links between the deleted node and its parent and children. In the most general case, we end up with three disconnected BSTs, one that contains the deleted node's parent and two corresponding to the deleted node's former subtrees. The diagram below shows how this idea works out for the deletion of node 5 from the tree on the left:
Of course, the problem then becomes to reassemble the pieces into a single binary search tree. We can do this by merging the two former subtrees of the deleted node and attaching them as the right child of the parent subtree. As the first step in merging the subtrees, we take the minimum node r in the former right subtree and repeatedly perform a right rotation on its parent, until it is the root of its subtree. The process up to this point looks like this for our example, showing only the subtree containing r:
Now, because r is the root and the minimum node in its subtree, r has no left child. Also, all the nodes in the opposite subtree are smaller than r. So to merge these subtrees, we simply link the opposite subtree as r's left child and connect r in place of the deleted node:
The function outline is straightforward:
First we search for the node to delete, storing it as p and its parent as q:
p = (struct bst_node *) &tree->bst_root; for (cmp = -1; cmp != 0; |
The actual deletion process is not as simple. We handle specially the case where p has no right child. This is unfortunate for uniformity, but simplifies the rest of the code considerably. The main case starts off with a loop on variable r to build a stack of the nodes in the right subtree of p that will need to be rotated. After the loop, r is the minimum value in p's right subtree. This will be the new root of the merged subtrees after the rotations, so we set r as q's child on the appropriate side and r's left child as p's former left child. After that the only remaining task is the rotations themselves, so we perform them and we're done:
if (p->bst_link[1] != NULL) |
Finally, there's a bit of obligatory bookkeeping:
item = p->bst_data; tree->bst_alloc->libavl_free (tree->bst_alloc, p); tree->bst_count--; tree->bst_generation++; |
See also: [ Sedgewick 1998], section 12.9.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |