GNU libavl 2.0.1
10.4.2 Step 2: Delete
The code for node deletion is a combination of RB deletion
(see section 7.5.1 Step 2: Delete) and TBST deletion
(see section 8.7 Deletion). The node to delete is p, and after
deletion the stack contains all the nodes down to where rebalancing
begins. The cases are the same as for TBST deletion:
 if (p>trb_tag[1] == TRB_THREAD) {
if (p>trb_tag[0] == TRB_CHILD)
{ <@xref{\NODE\, , Case 1 in TRB deletion.>,352} }
else { <@xref{\NODE\, , Case 2 in TRB deletion.>,353} }
} else {
enum trb_color t;
struct trb_node *r = p>trb_link[1];
if (r>trb_tag[0] == TRB_THREAD)
{ <@xref{\NODE\, , Case 3 in TRB deletion.>,354} }
else { <@xref{\NODE\, , Case 4 in TRB deletion.>,355} }
}

This code is included in @refalso{349
Case 1: p has a right thread and a left child
If the node to delete p has a right thread and a left child, then we
replace it by its left child. We also have to chase down the right
thread that pointed to p. The code is almost the same as <@xref{\NODE\, , \TITLE\}.>{Case 1 in
TBST deletion,260}, but we use the stack here instead of a single parent
pointer.
 struct trb_node *t = p>trb_link[0];
while (t>trb_tag[1] == TRB_CHILD)
t = t>trb_link[1];
t>trb_link[1] = p>trb_link[1];
pa[k  1]>trb_link[da[k  1]] = p>trb_link[0];

This code is included in @refalso{351
Case 2: p has a right thread and a left thread
Deleting a leaf node is the same process as for a TBST. The changes
from <@xref{\NODE\, , Case 2 in TBST deletion.>,261} are again due to the use of a stack.
 pa[k  1]>trb_link[da[k  1]] = p>trb_link[da[k  1]];
if (pa[k  1] != (struct trb_node *) &tree>trb_root)
pa[k  1]>trb_tag[da[k  1]] = TRB_THREAD;

This code is included in @refalso{351
Case 3: p's right child has a left thread
The code for case 3 merges <@xref{\NODE\, , Case 3 in TBST deletion.>,262} with <@xref{\NODE\, , \TITLE\}.>{Case 2
in RB deletion,223}. First, the node is deleted in the same way used for
a TBST. Then the colors of p and r are swapped, and r is added
to the stack, in the same way as for RB deletion.
 r>trb_link[0] = p>trb_link[0];
r>trb_tag[0] = p>trb_tag[0];
if (r>trb_tag[0] == TRB_CHILD) {
struct trb_node *t = r>trb_link[0];
while (t>trb_tag[1] == TRB_CHILD)
t = t>trb_link[1];
t>trb_link[1] = r;
}
pa[k  1]>trb_link[da[k  1]] = r;
t = r>trb_color;
r>trb_color = p>trb_color;
p>trb_color = t;
da[k] = 1;
pa[k++] = r;

This code is included in @refalso{351
Case 4: p's right child has a left child
Case 4 is a mix of <@xref{\NODE\, , Case 4 in TBST deletion.>,263} and <@xref{\NODE\, , \TITLE\}.>{Case 3 in RB
deletion,224}. It follows the outline of TBST deletion, but updates the
stack. After the deletion it also swaps the colors of p and s as
in RB deletion.
 struct trb_node *s;
int j = k++;
for (;;) {
da[k] = 0;
pa[k++] = r;
s = r>trb_link[0];
if (s>trb_tag[0] == TRB_THREAD)
break;
r = s;
}
da[j] = 1;
pa[j] = s;
if (s>trb_tag[1] == TRB_CHILD)
r>trb_link[0] = s>trb_link[1];
else {
r>trb_link[0] = s;
r>trb_tag[0] = TRB_THREAD;
}
s>trb_link[0] = p>trb_link[0];
if (p>trb_tag[0] == TRB_CHILD) {
struct trb_node *t = p>trb_link[0];
while (t>trb_tag[1] == TRB_CHILD)
t = t>trb_link[1];
t>trb_link[1] = s;
s>trb_tag[0] = TRB_CHILD;
}
s>trb_link[1] = p>trb_link[1];
s>trb_tag[1] = TRB_CHILD;
t = s>trb_color;
s>trb_color = p>trb_color;
p>trb_color = t;
pa[j  1]>trb_link[da[j  1]] = s;

This code is included in @refalso{351
Exercises:
1. Rewrite <@xref{\NODE\, , Case 4 in TAVL deletion.>,317} to replace the deleted node's
tavl_data by its successor, then delete the successor, instead of
shuffling pointers. (Refer back to Exercise 4.83 for an
explanation of why this approach cannot be used in libavl.)
[answer]