11.5.2 Step 2: Delete

As demonstrated in the previous chapter, left-looking deletion, where we examine the left subtree of the node to be deleted, is more efficient than right-looking deletion in an RTBST (see Left-Looking Deletion in an RTBST). This holds true in an RTAVL tree, too.

433. <Step 2: Delete RTAVL node 433> =
if (p->rtavl_link[0] == NULL) 
  {
    if (p->rtavl_rtag == RTAVL_CHILD)
      { 
        <Case 1 in RTAVL deletion 434> 
      }
    else 
      { 
        <Case 2 in RTAVL deletion 435> 
      }
  } 
else 
  {
    struct rtavl_node *r = p->rtavl_link[0];
    if (r->rtavl_rtag == RTAVL_THREAD)
      { 
        <Case 3 in RTAVL deletion 436> 
      }
    else 
      { 
        <Case 4 in RTAVL deletion 437> 
      }
  }

tree->rtavl_alloc->libavl_free (tree->rtavl_alloc, p);

This code is included in 431.

Case 1: p has a right child but no left child

If the node to be deleted, p, has a right child but not a left child, then we replace it by its right child.

434. <Case 1 in RTAVL deletion 434> =
pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[1];

This code is included in 433 and 472.

Case 2: p has a right thread and no left child

If we are deleting a leaf, then we replace it by a null pointer if it's a left child, or by a pointer to its own former right thread if it's a right child. Refer back to the commentary on <Case 2 in right-looking RTBST deletion 387> for further explanation.

435. <Case 2 in RTAVL deletion 435> =
pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[da[k - 1]];
if (da[k - 1] == 1)
  pa[k - 1]->rtavl_rtag = RTAVL_THREAD;

This code is included in 433 and 473.

Case 3: p's left child has a right thread

If p has a left child r, and r has a right thread, then we replace p by r and transfer p's former right link to r. Node r also receives p's balance factor.

436. <Case 3 in RTAVL deletion 436> =
r->rtavl_link[1] = p->rtavl_link[1];
r->rtavl_rtag = p->rtavl_rtag;
r->rtavl_balance = p->rtavl_balance;
pa[k - 1]->rtavl_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;

This code is included in 433.

Case 4: p's left child has a right child

The final case, where node p's left child r has a right child, is also the most complicated. We find p's predecessor s first:

437. <Case 4 in RTAVL deletion 437> =
struct rtavl_node *s;
int j = k++;

for (;;) 
  {
    da[k] = 1;
    pa[k++] = r;
    s = r->rtavl_link[1];
    if (s->rtavl_rtag == RTAVL_THREAD)
      break;

    r = s;
  }

See also 438 and 439.

Then we move s into p's place, not forgetting to update links and tags as necessary:

438. <Case 4 in RTAVL deletion 437> +=
da[j] = 0;
pa[j] = pa[j - 1]->rtavl_link[da[j - 1]] = s;

if (s->rtavl_link[0] != NULL)
  r->rtavl_link[1] = s->rtavl_link[0];
else 
  {
    r->rtavl_rtag = RTAVL_THREAD;
    r->rtavl_link[1] = s;
  }

Finally, we copy p's old information into s, except for the actual data:

439. <Case 4 in RTAVL deletion 437> +=
s->rtavl_balance = p->rtavl_balance;
s->rtavl_link[0] = p->rtavl_link[0];
s->rtavl_link[1] = p->rtavl_link[1];
s->rtavl_rtag = p->rtavl_rtag;