11.5.4 Step 4: Rebalance |

Rebalancing in an RTAVL tree after deletion is not completely symmetric
between left-side and right-side rebalancing, but there are pairs of
similar subcases on each side. The outlines are similar, too. Either
way, rebalancing occurs at node *y*, and cases are distinguished based
on the balance factor of *x*, the child of *y* on the side opposite the
deletion.

439. <Step 4: Rebalance after RTAVL deletion in left subtree 439> =structrtavl_node*x=y->rtavl_link[1];assert(x!=NULL);if(x->rtavl_balance== -1)

{ <Rebalance for - balance factor after left-side RTAVL deletion 441> }else

{pa[k- 1]->rtavl_link[da[k- 1]] =x;if(x->rtavl_balance== 0)

{ <Rebalance for 0 balance factor after left-side RTAVL deletion 443>break; }else/*x->rtavl_balance== +1 */

{ <Rebalance for + balance factor after left-side RTAVL deletion 445> } }

This code is included in 438.

440. <Step 4: Rebalance after RTAVL deletion in right subtree 440> =structrtavl_node*x=y->rtavl_link[0];assert(x!=NULL);if(x->rtavl_balance== +1)

{ <Rebalance for + balance factor after right-side RTAVL deletion 442> }else

{pa[k- 1]->rtavl_link[da[k- 1]] =x;if(x->rtavl_balance== 0)

{ <Rebalance for 0 balance factor after right-side RTAVL deletion 444>break; }else/*x->rtavl_balance== -1 */

{ <Rebalance for - balance factor after right-side RTAVL deletion 446> } }

This code is included in 438.

If the taller subtree of *x* is on the same side as the deletion, then
we rotate at *x* in the opposite direction from the deletion, then at
*y* in the same direction as the deletion. This is the same as case 2
for RTAVL insertion (see rtavlinscase2), which in turn performs
the general transformation described for AVL deletion case 1
(see avldelcase1), and we can reuse the code.

441. <Rebalance for - balance factor after left-side RTAVL deletion 441> =structrtavl_node*w; <Rebalance for - balance factor in RTAVL insertion in right subtree 428>pa[k- 1]->rtavl_link[da[k- 1]] =w;

This code is included in 439.

442. <Rebalance for + balance factor after right-side RTAVL deletion 442> =structrtavl_node*w; <Rebalance for + balance factor in RTAVL insertion in left subtree 427>pa[k- 1]->rtavl_link[da[k- 1]] =w;

This code is included in 440.

If *x*'s two subtrees are of equal height, then we perform a rotation at
*y* toward the deletion. This rotation cannot be troublesome, for the
same reason discussed for rebalancing in TAVL trees
(see tavldelcase2). We can even reuse the code:

443. <Rebalance for 0 balance factor after left-side RTAVL deletion 443> = <Rebalance for 0 balance factor after TAVL deletion in left subtree; tavl => rtavl 321>

This code is included in 439.

444. <Rebalance for 0 balance factor after right-side RTAVL deletion 444> = <Rebalance for 0 balance factor after TAVL deletion in right subtree; tavl => rtavl 325>

This code is included in 440.

When *x*'s taller subtree is on the side opposite the deletion, we
rotate at *y* toward the deletion, same as case 2. If the deletion was
on the left side of *y*, then the general form is the same as for TAVL
deletion (see tavldelcase3). The special case for left-side
deletion, where *x* lacks a left child, and the general form of the
code, are shown here:

445. <Rebalance for + balance factor after left-side RTAVL deletion 445> =if(x->rtavl_link[0] !=NULL)y->rtavl_link[1] =x->rtavl_link[0];else

y->rtavl_rtag=RTAVL_THREAD;x->rtavl_link[0] =y;y->rtavl_balance=x->rtavl_balance= 0;

This code is included in 439.

The special case for right-side deletion, where *x* lacks a right child,
and the general form of the code, are shown here:

446. <Rebalance for - balance factor after right-side RTAVL deletion 446> =if(x->rtavl_rtag==RTAVL_CHILD)y->rtavl_link[0] =x->rtavl_link[1];else

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

This code is included in 440.

**Exercises:**

**1.** In the chapter about TAVL deletion, we offered two implementations of
deletion: one using a stack (<TAVL item deletion function, with stack 659>) and one using an algorithm to find node parents (<TAVL item deletion function 311>). For RTAVL deletion, we offer only a stack-based
implementation. Why?
[answer]

**2.** The introduction to this section states that left-looking deletion is
more efficient than right-looking deletion in an RTAVL tree. Confirm
this by writing a right-looking alternate implementation of <Step 2: Delete RTAVL node 431> and comparing the two sets of code.
[answer]

**3.** Rewrite <Case 4 in RTAVL deletion 435> to replace the deleted node's
*rtavl_data* by its successor, then delete the successor, instead of
shuffling pointers. (Refer back to Exercise 4.8-3 for an
explanation of why this approach cannot be used in libavl.)
[answer]