GNU libavl 2.0.1
12.5.4 Step 4: Rebalance
Rebalancing in an RTAVL tree after deletion is not completely symmetric
between leftside and rightside rebalancing, but there are pairs of
similar subcases on each side. The outlines are similar, too. Either
way, rebalancing occurs at node y, and cases are distinguished based
on the balance factor of x, the child of y on the side opposite the
deletion.
 struct rtavl_node *x = y>rtavl_link[1];
assert (x != NULL);
if (x>rtavl_balance == 1) {
<@xref{\NODE\, , Rebalance for .> balance factor after leftside RTAVL deletion,441}
} else {
pa[k  1]>rtavl_link[da[k  1]] = x;
if (x>rtavl_balance == 0) {
<@xref{\NODE\, , Rebalance for 0 balance factor after leftside RTAVL deletion.>,443}
break;
}
else /* x>rtavl_balance == +1 */ {
<@xref{\NODE\, , Rebalance for +.> balance factor after leftside RTAVL deletion,445}
}
}

This code is included in @refalso{438
 struct rtavl_node *x = y>rtavl_link[0];
assert (x != NULL);
if (x>rtavl_balance == +1) {
<@xref{\NODE\, , Rebalance for +.> balance factor after rightside RTAVL deletion,442}
} else {
pa[k  1]>rtavl_link[da[k  1]] = x;
if (x>rtavl_balance == 0) {
<@xref{\NODE\, , Rebalance for 0 balance factor after rightside RTAVL deletion.>,444}
break;
}
else /* x>rtavl_balance == 1 */ {
<@xref{\NODE\, , Rebalance for .> balance factor after rightside RTAVL deletion,446}
}
}

This code is included in @refalso{438
Case 1: x has taller subtree on same side as deletion
If the taller subtree of x is on the same side as the deletion, then
we rotate at x in the opposite direction from the deletion, then at
y in the same direction as the deletion. This is the same as case 2
for RTAVL insertion (@pageref{rtavlinscase2}), which in turn performs
the general transformation described for AVL deletion case 1
(@pageref{avldelcase1}), and we can reuse the code.
 struct rtavl_node *w;
<@xref{\NODE\, , Rebalance for .> balance factor in RTAVL insertion in right subtree,428}
pa[k  1]>rtavl_link[da[k  1]] = w;

This code is included in @refalso{439
 struct rtavl_node *w;
<@xref{\NODE\, , Rebalance for +.> balance factor in RTAVL insertion in left subtree,427}
pa[k  1]>rtavl_link[da[k  1]] = w;

This code is included in @refalso{440
Case 2: x's subtrees are equal height
If x's two subtrees are of equal height, then we perform a rotation at
y toward the deletion. This rotation cannot be troublesome, for the
same reason discussed for rebalancing in TAVL trees
(@pageref{tavldelcase2}). We can even reuse the code:
 <@xref{\NODE\, , Rebalance for 0 balance factor after TAVL deletion in left subtree; tavl =>.> rtavl,321}

This code is included in @refalso{439
 <@xref{\NODE\, , Rebalance for 0 balance factor after TAVL deletion in right subtree; tavl =>.> rtavl,325}

This code is included in @refalso{440
Case 3: x has taller subtree on side opposite deletion
When x's taller subtree is on the side opposite the deletion, we
rotate at y toward the deletion, same as case 2. If the deletion was
on the left side of y, then the general form is the same as for TAVL
deletion (@pageref{tavldelcase3}). The special case for leftside
deletion, where x lacks a left child, and the general form of the
code, are shown here:
 if (x>rtavl_link[0] != NULL)
y>rtavl_link[1] = x>rtavl_link[0];
else y>rtavl_rtag = RTAVL_THREAD;
x>rtavl_link[0] = y;
y>rtavl_balance = x>rtavl_balance = 0;

This code is included in @refalso{439
The special case for rightside deletion, where x lacks a right child,
and the general form of the code, are shown here:
 if (x>rtavl_rtag == RTAVL_CHILD)
y>rtavl_link[0] = x>rtavl_link[1];
else {
y>rtavl_link[0] = NULL;
x>rtavl_rtag = RTAVL_CHILD;
}
x>rtavl_link[1] = y;
y>rtavl_balance = x>rtavl_balance = 0;

This code is included in @refalso{440
Exercises:
1. In the chapter about TAVL deletion, we offered two implementations of
deletion: one using a stack (<@xref{\NODE\, , \TITLE\}.>{TAVL item deletion function, with
stack,659}) and one using an algorithm to find node parents (<@xref{\NODE\, , \TITLE\}.>{TAVL item
deletion function,311}). For RTAVL deletion, we offer only a stackbased
implementation. Why?
[answer]
2. The introduction to this section states that leftlooking deletion is
more efficient than rightlooking deletion in an RTAVL tree. Confirm
this by writing a rightlooking alternate implementation of <@xref{\NODE\, , \TITLE\}.>{Step 2:
Delete RTAVL node,431} and comparing the two sets of code.
[answer]
3. Rewrite <@xref{\NODE\, , Case 4 in RTAVL deletion.>,435} to replace the deleted node's
rtavl_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]