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


GNU libavl 2.0.1

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

6.4.4 Step 4: Rebalance

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-&#62;avl_balance == -2)
  { 
&#60;@xref{\NODE\, , Rebalance AVL tree after insertion in left subtree.&#62;,152}
} else if (y-&#62;avl_balance == +2) {
&#60;@xref{\NODE\, , Rebalance AVL tree after insertion in right subtree.&#62;,157}
} else
return &n-&#62;avl_data;
See also @refalso{153 This code is included in @refalso{146

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-&#62;avl_link[0];
if (x-&#62;avl_balance == -1)
  { 
&#60;@xref{\NODE\, , Rotate right at y.&#62; in AVL tree,155}
} else
{
&#60;@xref{\NODE\, , Rotate left at x.&#62; then right at y in AVL tree,156}
}
This code is included in @refalso{151

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-&#62;avl_link[y != z-&#62;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-&#62;avl_generation++;
return &n-&#62;avl_data;

Case 1: x has - balance factor

For a - balance factor, we just rotate right at y. Then the entire process, including insertion and rebalancing, looks like this:

avlcase1

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-&#62;avl_link[0] = x-&#62;avl_link[1];
x-&#62;avl_link[1] = y;
x-&#62;avl_balance = y-&#62;avl_balance = 0;
This code is included in @refalso{152

Case 2: x has + balance factor

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:

avlcase2

At the beginning, the figure does not show the balance factor of w. This is because there are three possibilities:

Case 2.1: w has balance factor 0.
This means that w is the new node. a, b, c, and d have height 0. After the rotations, x and y have balance factor 0.

Case 2.2: w has balance factor -.
a, b, and d have height h > 0, and c has height h - 1.

Case 2.3: w has balance factor +.
a, c, and d have height h > 0, and b has height h - 1.

 
assert (x-&#62;avl_balance == +1);
w = x-&#62;avl_link[1];
x-&#62;avl_link[1] = w-&#62;avl_link[0];
w-&#62;avl_link[0] = x;
y-&#62;avl_link[0] = w-&#62;avl_link[1];
w-&#62;avl_link[1] = y;
if (w-&#62;avl_balance == -1) 
x-&#62;avl_balance = 0, y-&#62;avl_balance = +1; else if (w-&#62;avl_balance == 0)
x-&#62;avl_balance = y-&#62;avl_balance = 0; else /* w-&#62;avl_balance == +1 */
x-&#62;avl_balance = -1, y-&#62;avl_balance = 0; w-&#62;avl_balance = 0;
This code is included in @refalso{152

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-&#62;avl_link[y != z-&#62;avl_link[0]] = w in the second part of &#60;@xref{\NODE\, , Step 4: Rebalance after AVL insertion.&#62;,151} above. Why would it be a bad idea to substitute the apparent equivalent z-&#62;avl_link[y == z-&#62;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