5.5.4 Step 4: Rebalance |

Now we have to write code to rebalance when it becomes necessary.
We'll use rotations to do this, as before. Again, we'll distinguish
the cases on the basis of *x*'s balance factor, where *x* is *y*'s
right child:

173. <Step 4: Rebalance after AVL deletion 173> =structavl_node*x=y->avl_link[1];if(x->avl_balance== -1) {

<Left-side rebalancing case 1 in AVL deletion 174>

}else

{

<Left-side rebalancing case 2 in AVL deletion 175>

}

This code is included in 172.

If *x* has a - balance factor, we handle rebalancing in a manner
analogous to case 2 for insertion. In fact, we reuse the code. We
rotate right at *x*, then left at *y*. *w* is the left child of *x*.
The two rotations look like this:

174. <Left-side rebalancing case 1 in AVL deletion 174> =structavl_node*w; <Rotate right atxthen left atyin AVL tree 159>pa[k- 1]->avl_link[da[k- 1]] =w;

This code is included in 173.

When *x*'s balance factor is +, the needed treatment is analogous to
Case 1 for insertion. We simply rotate left at *y* and update the
pointer to the subtree, then update balance factors. The deletion and
rebalancing then look like this:

When *x*'s balance factor is 0, we perform the same rotation, but the
height of the overall subtree does not change, so we're done and can
exit the loop with **break**. Here's what the deletion and rebalancing
look like for this subcase:

175. <Left-side rebalancing case 2 in AVL deletion 175> =y->avl_link[1] =x->avl_link[0];x->avl_link[0] =y;pa[k- 1]->avl_link[da[k- 1]] =x;if(x->avl_balance== 0)

{x->avl_balance= -1;y->avl_balance= +1;break; }else

x->avl_balance=y->avl_balance= 0;

This code is included in 173.

**Exercises:**

**1.** In <Step 4: Rebalance after AVL deletion 173>, we refer to fields in
*x*, the right child of *y*, without checking that *y* has a non-null
right child. Why can we assume that node *x* is non-null?
[answer]

**2.** Describe the shape of a tree that might require rebalancing at every
level above a particular node. Give an example.
[answer]