8.4.2 Step 4: Rebalance |

Now we're finally to the interesting part, the rebalancing step. We
can tell whether rebalancing is necessary based on the balance factor
of *y*, the same as in unthreaded AVL insertion:

306. <Step 4: Rebalance after TAVL insertion 306> =if(y->tavl_balance== -2) {

<Rebalance TAVL tree after insertion in left subtree 307>

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

<Rebalance TAVL tree after insertion in right subtree 310>

}else

return&n->tavl_data;z->tavl_link[y!=z->tavl_link[0]] =w;return&n->tavl_data;

This code is included in 303.

We will examine the case of insertion in the left subtree of *y*, the
node at which we must rebalance. We take *x* as *y*'s child on the
side of the new node, then, as for unthreaded AVL insertion, we
distinguish two cases based on the balance factor of *x*:

307. <Rebalance TAVL tree after insertion in left subtree 307> =structtavl_node*x=y->tavl_link[0];if(x->tavl_balance== -1) {

<Rebalance for - balance factor in TAVL insertion in left subtree 308>

}else

{

<Rebalance for + balance factor in TAVL insertion in left subtree 309>

}

This code is included in 306.

As for unthreaded insertion, we rotate right at *y* (see Rebalancing AVL Trees). Notice the resemblance of the following code to
*rotate_right*() in the solution to Exercise 8.2-1.

308. <Rebalance for - balance factor in TAVL insertion in left subtree 308> =w=x;if(x->tavl_tag[1] ==TAVL_THREAD)

{x->tavl_tag[1] =TAVL_CHILD;y->tavl_tag[0] =TAVL_THREAD;y->tavl_link[0] =x; }else

y->tavl_link[0] =x->tavl_link[1];x->tavl_link[1] =y;x->tavl_balance=y->tavl_balance= 0;

This code is included in 307.

When *x* has a + balance factor, we perform the transformation shown
below, which consists of a left rotation at *x* followed by a right
rotation at *y*. This is the same transformation used in unthreaded
insertion:

We could simply apply the standard code from Exercise 8.2-1 in each
rotation (see Exercise 1), but it is just as
straightforward to do both of the rotations together, then clean up
any threads. Subtrees *a* and *d* cannot cause thread-related
trouble, because they are not disturbed during the transformation: *a*
remains *x*'s left child and *d* remains *y*'s right child. The
children of *w*, subtrees *b* and *c*, do require handling. If
subtree *b* is a thread, then after the rotation and before fix-up
*x*'s right link points to itself, and, similarly, if *c* is a thread
then *y*'s left link points to itself. These links must be changed
into threads to *w* instead, and *w*'s links must be tagged as child
pointers.

If both *b* and *c* are threads then the transformation looks like the
diagram below, showing pre-rebalancing and post-rebalancing,
post-fix-up views. The AVL balance rule implies that if *b* and *c*
are threads then *a* and *d* are also:

The required code is heavily based on the corresponding code for unthreaded AVL rebalancing:

309. <Rebalance for + balance factor in TAVL insertion in left subtree 309> = <Rotate left atxthen right atyin AVL tree; avl => tavl 158>if(w->tavl_tag[0] ==TAVL_THREAD)

{x->tavl_tag[1] =TAVL_THREAD;x->tavl_link[1] =w;w->tavl_tag[0] =TAVL_CHILD; }if(w->tavl_tag[1] ==TAVL_THREAD)

{y->tavl_tag[0] =TAVL_THREAD;y->tavl_link[0] =w;w->tavl_tag[1] =TAVL_CHILD; }

This code is included in 307, 326, and 669.

**Exercises:**

**1.** Rewrite <Rebalance for + balance factor in TAVL insertion in left subtree 309> in terms of the routines from Exercise 8.2-1.
[answer]