www.delorie.com/gnu/docs/avl/libavl_97.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
We've covered steps 1 through 3 so far. Step 4, rebalancing, is somewhat complicated, but it's the key to the entire insertion procedure. It is also similar to, but simpler than, other rebalancing procedures we'll see later. As a result, we're going to discuss it in detail. Follow along carefully and it should all make sense.
Before proceeding, let's briefly review the circumstances under which we need to rebalance. Looking back a few sections, we see that there is only one case where this is required: case 3, when the new node is added in the taller subtree of a node with nonzero balance factor.
Case 3 is the case where y has a -2 or +2 balance factor after insertion. For now, we'll just consider the -2 case, because we can write code for the +2 case later in a mechanical way by applying the principle of symmetry. In accordance with this idea, step 4 branches into three cases immediately, one for each rebalancing case and a third that just returns from the function if no rebalancing is necessary:
if (y->avl_balance == -2) { |
We will call y's left child x. The new node is somewhere in the subtrees of x. There are now only two cases of interest, distinguished on whether x has a + or - balance factor. These cases are almost entirely separate:
struct avl_node *x = y->avl_link[0]; if (x->avl_balance == -1) { |
In either case, w receives the root of the rebalanced subtree, which is used to update the parent's pointer to the subtree root (recall that z is the parent of y):
z->avl_link[y != z->avl_link[0]] = w; |
Finally, we increment the generation number, because the tree's structure has changed. Then we're done and we return to the caller:
tree->avl_generation++; return &n->avl_data; |
For a - balance factor, we just rotate right at y. Then the entire process, including insertion and rebalancing, looks like this:
This figure also introduces a new graphical convention. The change in subtree a between the first and second diagrams is indicated by an asterisk (*).(12) In this case, it indicates that the new node was inserted in subtree a.
The code here is similar to rotate_right() in the solution to Exercise 4.3-2:
w = x; y->avl_link[0] = x->avl_link[1]; x->avl_link[1] = y; x->avl_balance = y->avl_balance = 0; |
This case is just a little more intricate. First, let x's right child be w. Either w is the new node, or the new node is in one of w's subtrees. To restore balance, we rotate left at x, then rotate right at y (this is a kind of "double rotation"). The process, starting just after the insertion and showing the results of each rotation, looks like this:
At the beginning, the figure does not show the balance factor of w. This is because there are three possibilities:
assert (x->avl_balance == +1); w = x->avl_link[1]; x->avl_link[1] = w->avl_link[0]; w->avl_link[0] = x; y->avl_link[0] = w->avl_link[1]; w->avl_link[1] = y; if (w->avl_balance == -1) |
Exercises:
1. Why can't the new node be x rather than a node in x's subtrees? [answer]
2. Why can't x have a 0 balance factor? [answer]
3. For each subcase of case 2, draw a figure like that given for generic case 2 that shows the specific balance factors at each step. [answer]
4. Explain the expression z->avl_link[y != z->avl_link[0]] = w in the second part of <@xref{\NODE\, , Step 4: Rebalance after AVL insertion.>,151} above. Why would it be a bad idea to substitute the apparent equivalent z->avl_link[y == z->avl_link[1]] = w? [answer]
5. Suppose that we wish to make a copy of an AVL tree, preserving the original tree's shape, by inserting nodes from the original tree into a new tree, using avl_probe(). Will inserting the original tree's nodes in level order (see the answer to Exercise 4.7-4) have the desired effect? [answer]
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |