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

153. <Step 4: Rebalance after AVL insertion 153> =
if (y->avl_balance == -2)
  { 
    <Rebalance AVL tree after insertion in left subtree 154> 
  }
else if (y->avl_balance == +2)
  { 
    <Rebalance AVL tree after insertion in right subtree 159> 
  }
else 
  return &n->avl_data;

See also 155 and 156.

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:

154. <Rebalance AVL tree after insertion in left subtree 154> =
struct avl_node *x = y->avl_link[0];
if (x->avl_balance == -1)
  { 
    <Rotate right at y in AVL tree 157> 
  }
else 
  { 
    <Rotate left at x then right at y in AVL tree 158> 
  }

This code is included in 153 and 164.

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

155. <Step 4: Rebalance after AVL insertion 153> +=
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:

156. <Step 4: Rebalance after AVL insertion 153> +=
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 (*).¹ 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:

157. <Rotate right at y in AVL tree 157> =
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 154 and 531.

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.

158. <Rotate left at x then right at y in AVL tree 158> =
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 154, 179, 309, 429, and 532.

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 <Step 4: Rebalance after AVL insertion 153> 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]