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_rtag == RTAVL_CHILD)
{         <Case 1 in RTAVL deletion 434>       }
else       {         <Case 2 in RTAVL deletion 435>       }
} else   {
{         <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> =
```

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> =
if (da[k - 1] == 1)
```

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_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;
break;

r = s;
}
```

This code is included in 433.

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;

else   {
```439. <Case 4 in RTAVL deletion 437> +=