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:

151. <Step 4: Rebalance after AVL insertion 151> =if(y->avl_balance== -2) {

<Rebalance AVL tree after insertion in left subtree 152>

}elseif(y->avl_balance== +2) {

<Rebalance AVL tree after insertion in right subtree 157>

}else

return&n->avl_data;

This code is included in 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:

152. <Rebalance AVL tree after insertion in left subtree 152> =structavl_node*x=y->avl_link[0];if(x->avl_balance== -1) {

<Rotate right atyin AVL tree 155>

}else

{

<Rotate left atxthen right atyin AVL tree 156>

}

This code is included in 151 and 162.

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

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

154. <Step 4: Rebalance after AVL insertion 151> +=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 (*).^{1}
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:

155. <Rotate right atyin AVL tree 155> =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 152 and 529.

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.

156. <Rotate left atxthen right atyin AVL tree 156> =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;elseif(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 152, 177, 307, 427, and 530.

**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 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]