www.delorie.com/gnu/docs/avl/libavl_97.html

search

	Buy GNU books!

GNU libavl 2.0.1

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->avl_balance == -2) { <@xref{\NODE\, , Rebalance AVL tree after insertion in left subtree.>,152} } else if (y->avl_balance == +2) { <@xref{\NODE\, , Rebalance AVL tree after insertion in right subtree.>,157} } else return &n->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->avl_link[0]; if (x->avl_balance == -1) { <@xref{\NODE\, , Rotate right at y.> in AVL tree,155} } else { <@xref{\NODE\, , Rotate left at x.> 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->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;

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:

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 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:

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->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) x->avl_balance = 0, y->avl_balance = +1; else if (w->avl_balance == 0) x->avl_balance = y->avl_balance = 0; else /* w->avl_balance == +1 */ x->avl_balance = -1, y->avl_balance = 0; w->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->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]