11.4.2 Step 4: Rebalance |

Unlike all of the AVL rebalancing algorithms we've seen so far, rebalancing of a right-threaded AVL tree is not symmetric. This means that we cannot single out left-side rebalancing or right-side rebalancing as we did before, hand-waving the rest of it as a symmetric case. But both cases are very similar, if not exactly symmetric, so we will present the corresponding cases together. The theory is exactly the same as before (see Rebalancing AVL Trees). Here is the code to choose between left-side and right-side rebalancing:

424. <Step 4: Rebalance after RTAVL insertion 424> =if(y->rtavl_balance== -2) {

<Step 4: Rebalance RTAVL tree after insertion to left 425>

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

<Step 4: Rebalance RTAVL tree after insertion to right 426>

}else

return&n->rtavl_data;z->rtavl_link[y!=z->rtavl_link[0]] =w;return&n->rtavl_data;

This code is included in 421.

The code to choose between the two subcases within the left-side and
right-side rebalancing cases follows below. As usual during
rebalancing, *y* is the node at which rebalancing occurs, *x* is its
child on the same side as the inserted node, and cases are
distinguished on the basis of *x*'s balance factor:

425. <Step 4: Rebalance RTAVL tree after insertion to left 425> =structrtavl_node*x=y->rtavl_link[0];if(x->rtavl_balance== -1) {

<Rebalance for - balance factor in RTAVL insertion in left subtree 427>

}else

{

<Rebalance for + balance factor in RTAVL insertion in left subtree 429>

}

This code is included in 424.

426. <Step 4: Rebalance RTAVL tree after insertion to right 426> =structrtavl_node*x=y->rtavl_link[1];if(x->rtavl_balance== +1) {

<Rebalance for + balance factor in RTAVL insertion in right subtree 428>

}else

{

<Rebalance for - balance factor in RTAVL insertion in right subtree 430>

}

This code is included in 424.

If node *x*'s taller subtree is on the same side as the inserted node,
then we perform a rotation at *y* in the opposite direction. That is,
if the insertion occurred in the left subtree of *y* and *x* has a -
balance factor, we rotate right at *y*, and if the insertion was to
the right and *x* has a + balance factor, we rotate left at *y*.
This changes the balance of both *x* and *y* to zero. None of this is
a change from unthreaded or fully threaded rebalancing. The
difference is in the handling of empty subtrees, that is, in the
rotation itself (see RTBST Rotations).

Here is a diagram of left-side rebalancing for the interesting case
where *x* has a right thread. Taken along with *x*'s - balance
factor, this means that *n*, the newly inserted node, must be *x*'s left
child. Therefore, subtree *x* has height 2, so *y* has no right child
(because it has a -2 balance factor). This chain of logic means that
we know exactly what the tree looks like in this particular subcase:

427. <Rebalance for - balance factor in RTAVL insertion in left subtree 427> =w=x;if(x->rtavl_rtag==RTAVL_THREAD)

{x->rtavl_rtag=RTAVL_CHILD;y->rtavl_link[0] =NULL; }else

y->rtavl_link[0] =x->rtavl_link[1];x->rtavl_link[1] =y;x->rtavl_balance=y->rtavl_balance= 0;

This code is included in 425.

Here is the diagram and code for the similar right-side case:

428. <Rebalance for + balance factor in RTAVL insertion in right subtree 428> =w=x;if(x->rtavl_link[0] ==NULL)

{y->rtavl_rtag=RTAVL_THREAD;y->rtavl_link[1] =x; }else

y->rtavl_link[1] =x->rtavl_link[0];x->rtavl_link[0] =y;x->rtavl_balance=y->rtavl_balance= 0;

This code is included in 426.

If node *x*'s taller subtree is on the side opposite the newly inserted
node, then we perform a double rotation: first rotate at *x* in the same
direction as the inserted node, then in the opposite direction at *y*.
This is the same as in a threaded or unthreaded tree, and indeed we can
reuse much of the code.

The case where the details differ is, as usual, where threads or null
child pointers are moved around. In the most extreme case for insertion
to the left, where *w* is a leaf, we know that *x* has no left child and
*s* no right child, and the situation looks like the diagram below
before and after the rebalancing step:

429. <Rebalance for + balance factor in RTAVL insertion in left subtree 429> = <Rotate left atxthen right atyin AVL tree; avl => rtavl 158>if(x->rtavl_link[1] ==NULL)

{x->rtavl_rtag=RTAVL_THREAD;x->rtavl_link[1] =w; }if(w->rtavl_rtag==RTAVL_THREAD)

{y->rtavl_link[0] =NULL;w->rtavl_rtag=RTAVL_CHILD; }

This code is included in 425 and 444.

Here is the code and diagram for right-side insertion rebalancing:

430. <Rebalance for - balance factor in RTAVL insertion in right subtree 430> = <Rotate right atxthen left atyin AVL tree; avl => rtavl 161>if(y->rtavl_link[1] ==NULL)

{y->rtavl_rtag=RTAVL_THREAD;y->rtavl_link[1] =w; }if(w->rtavl_rtag==RTAVL_THREAD)

{x->rtavl_link[0] =NULL;w->rtavl_rtag=RTAVL_CHILD; }