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> =
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 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> =
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 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.

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.

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

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:

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.

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:

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]