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.

441. <Step 4: Rebalance after RTAVL deletion in left subtree 441> =
struct rtavl_node *x = y->rtavl_link[1];

assert (x != NULL);
if (x->rtavl_balance == -1) 
  {
    <Rebalance for - balance factor after left-side RTAVL deletion 443>
  } 
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 445>
        break;
      }
    else /* x->rtavl_balance == +1 */ 
      {
        <Rebalance for + balance factor after left-side RTAVL deletion 447>
      }
  }

This code is included in 440.

442. <Step 4: Rebalance after RTAVL deletion in right subtree 442> =
struct rtavl_node *x = y->rtavl_link[0];

assert (x != NULL);
if (x->rtavl_balance == +1) 
  {
    <Rebalance for + balance factor after right-side RTAVL deletion 444>
  } 
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 446>
        break;
      }
    else /* x->rtavl_balance == -1 */ 
      {
        <Rebalance for - balance factor after right-side RTAVL deletion 448>
      }
  }

This code is included in 440.

Case 1: x has taller subtree on same side as deletion

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.

443. <Rebalance for - balance factor after left-side RTAVL deletion 443> =
struct rtavl_node *w;

<Rebalance for - balance factor in RTAVL insertion in right subtree 430>
pa[k - 1]->rtavl_link[da[k - 1]] = w;

This code is included in 441.

444. <Rebalance for + balance factor after right-side RTAVL deletion 444> =
struct rtavl_node *w;

<Rebalance for + balance factor in RTAVL insertion in left subtree 429>
pa[k - 1]->rtavl_link[da[k - 1]] = w;

This code is included in 442.

Case 2: x's subtrees are equal height

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:

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

This code is included in 441.

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

This code is included in 442.

Case 3: x has taller subtree on side opposite deletion

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:

447. <Rebalance for + balance factor after left-side RTAVL deletion 447> =
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 441.

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

448. <Rebalance for - balance factor after right-side RTAVL deletion 448> =
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 442.

Exercises:

1. In the chapter about TAVL deletion, we offered two implementations of deletion: one using a stack (<TAVL item deletion function, with stack 661>) and one using an algorithm to find node parents (<TAVL item deletion function 313>). 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 433> and comparing the two sets of code. [answer]

3. Rewrite <Case 4 in RTAVL deletion 437> 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]