8.5.4 Step 4: Rebalance |

Rebalancing after deletion in a TAVL tree divides into three cases. The
first of these is analogous to case 1 in unthreaded AVL deletion, the
other two to case 2 (see Inserting into a TBST). The cases are
distinguished, as usual, based on the balance factor of right child *x*
of the node *y* at which rebalancing occurs:

319. <Step 4: Rebalance after TAVL deletion 319> =structtavl_node*x=y->tavl_link[1];assert(x!=NULL);if(x->tavl_balance== -1)

{ <Rebalance for - balance factor after TAVL deletion in left subtree 320> }else

{q->tavl_link[dir] =x;if(x->tavl_balance== 0)

{ <Rebalance for 0 balance factor after TAVL deletion in left subtree 321>break; }

else/*x->tavl_balance== +1 */

{ <Rebalance for + balance factor after TAVL deletion in left subtree 322> } }

This code is included in 318.

This case is just like case 2 in TAVL insertion. In fact, we can even reuse the code:

320. <Rebalance for - balance factor after TAVL deletion in left subtree 320> =structtavl_node*w; <Rebalance for - balance factor in TAVL insertion in right subtree 310>q->tavl_link[dir] =w;

This code is included in 319.

If *x* has a 0 balance factor, then we perform a left rotation at *y*.
The transformation looks like this, with subtree heights listed under
their labels:

Subtree *b* is taller than subtree *a*, so even if *h* takes its
minimum value of 1, then subtree *b* has height *h* == 1 and,
therefore, it must contain at least one node and there is no need to
do any checking for threads. The code is simple:

321. <Rebalance for 0 balance factor after TAVL deletion in left subtree 321> =y->tavl_link[1] =x->tavl_link[0];x->tavl_link[0] =y;x->tavl_balance= -1;y->tavl_balance= +1;

This code is included in 319 and 443.

If *x* has a + balance factor, we perform a left rotation at *y*, same
as for case 2, and the transformation looks like this:

One difference from case 2 is in the resulting balance factors. The
other is that if *h* == 1, then subtrees *a* and *b* have height *h* - 1 == 0, so *a* and *b* may actually be threads. In that case, the
transformation must be done this way:

This code handles both possibilities:

322. <Rebalance for + balance factor after TAVL deletion in left subtree 322> =if(x->tavl_tag[0] ==TAVL_CHILD)y->tavl_link[1] =x->tavl_link[0];else

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

This code is included in 319.