GNU libavl 2.0.1
9.5.2 Step 2: Delete
The cases for deletion are the same as for a TBST (see section 8.7 Deletion). The difference is that we have to copy around balance factors
and keep track of where balancing needs to start. After the deletion,
q is the node at which balance factors must be updated and possible
rebalancing occurs and dir is the side of q from which the node was
deleted. For cases 1 and 2, q need not change from its current value
as the parent of the deleted node. For cases 3 and 4, q will need to
be changed.
 if (p>tavl_tag[1] == TAVL_THREAD) {
if (p>tavl_tag[0] == TAVL_CHILD)
{ <@xref{\NODE\, , Case 1 in TAVL deletion.>,314} }
else { <@xref{\NODE\, , Case 2 in TAVL deletion.>,315} }
} else {
struct tavl_node *r = p>tavl_link[1];
if (r>tavl_tag[0] == TAVL_THREAD)
{ <@xref{\NODE\, , Case 3 in TAVL deletion.>,316} }
else { <@xref{\NODE\, , Case 4 in TAVL deletion.>,317} }
}
tree>tavl_alloc>libavl_free (tree>tavl_alloc, p);

This code is included in @refalso{311
Case 1: p has a right thread and a left child
If p has a right thread and a left child, then we replace it by its
left child. Rebalancing must begin right above p, which is already
set as q. There's no need to change the TBST code:
 <@xref{\NODE\, , Case 1 in TBST deletion; tbst =>.> tavl,260}

This code is included in @refalso{313
Case 2: p has a right thread and a left thread
If p is a leaf, then we change q's pointer to p into a thread.
Again, rebalancing must begin at the node that's already set up as q
and there's no need to change the TBST code:
 <@xref{\NODE\, , Case 2 in TBST deletion; tbst =>.> tavl,261}

This code is included in @refalso{313
Case 3: p's right child has a left thread
If p has a right child r, which in turn has no left child, then we
move r in place of p. In this case r, having replaced p,
acquires p's former balance factor and rebalancing must start from
there. The deletion in this case is always on the right side of the
node.
 <@xref{\NODE\, , Case 3 in TBST deletion; tbst =>.> tavl,262}
r>tavl_balance = p>tavl_balance;
q = r;
dir = 1;

This code is included in @refalso{313
Case 4: p's right child has a left child
The most general case comes up when p's right child has a left child,
where we replace p by its successor s. In that case s acquires
p's former balance factor and rebalancing begins from s's parent
r. Node s is always the left child of r.
 <@xref{\NODE\, , Case 4 in TBST deletion; tbst =>.> tavl,263}
s>tavl_balance = p>tavl_balance;
q = r;
dir = 0;

This code is included in @refalso{313
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]