GNU libavl 2.0.1
13.4.1 Step 2: Delete
We use leftlooking deletion. At this point, p is the node to delete.
After the deletion, x is the node that replaced p, or a null pointer
if the node was deleted without replacement. The cases are
distinguished in the usual way:
 if (p>rtrb_link[0] == NULL) {
if (p>rtrb_rtag == RTRB_CHILD)
{ <@xref{\NODE\, , Case 1 in RTRB deletion.>,470} }
else { <@xref{\NODE\, , Case 2 in RTRB deletion.>,471} }
} else {
enum rtrb_color t;
struct rtrb_node *r = p>rtrb_link[0];
if (r>rtrb_rtag == RTRB_THREAD)
{ <@xref{\NODE\, , Case 3 in RTRB deletion.>,472} }
else { <@xref{\NODE\, , Case 4 in RTRB deletion.>,473} }
}

This code is included in @refalso{468
Case 1: p has a right child but no left child
If p, the node to be deleted, has a right child but no left child,
then we replace it by its right child. This is the same as <@xref{\NODE\, , \TITLE\}.>{Case 1 in
RTAVL deletion,432}.
 <@xref{\NODE\, , Case 1 in RTAVL deletion; rtavl =>.> rtrb,432}

This code is included in @refalso{469
Case 2: p has a right thread and no left child
Similarly, case 2 is the same as <@xref{\NODE\, , Case 2 in RTAVL deletion.>,433}, with the
addition of an assignment to x.
 <@xref{\NODE\, , Case 2 in RTAVL deletion; rtavl =>.> rtrb,433}

This code is included in @refalso{469
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.
 r>rtrb_link[1] = p>rtrb_link[1];
r>rtrb_rtag = p>rtrb_rtag;
t = r>rtrb_color;
r>rtrb_color = p>rtrb_color;
p>rtrb_color = t;
pa[k  1]>rtrb_link[da[k  1]] = r;
da[k] = 0;
pa[k++] = r;

This code is included in @refalso{469
Case 4: p's left child has a right child
The fourth case, where p has a left child that itself has a right
child, uses the same algorithm as <@xref{\NODE\, , Case 4 in RTAVL deletion.>,435}, except
that instead of setting the balance factor of s, we swap the colors
of t and s as in <@xref{\NODE\, , Case 3 in RB deletion.>,224}.
 struct rtrb_node *s;
int j = k++;
for (;;) {
da[k] = 1;
pa[k++] = r;
s = r>rtrb_link[1];
if (s>rtrb_rtag == RTRB_THREAD)
break;
r = s;
}
da[j] = 0;
pa[j] = pa[j  1]>rtrb_link[da[j  1]] = s;
if (s>rtrb_link[0] != NULL)
r>rtrb_link[1] = s>rtrb_link[0];
else {
r>rtrb_rtag = RTRB_THREAD;
r>rtrb_link[1] = s;
}
s>rtrb_link[0] = p>rtrb_link[0];
s>rtrb_link[1] = p>rtrb_link[1];
s>rtrb_rtag = p>rtrb_rtag;
t = s>rtrb_color;
s>rtrb_color = p>rtrb_color;
p>rtrb_color = t;

This code is included in @refalso{469