GNU libavl 2.0.1
15.5.3 Step 4: Rebalance
The two cases for PAVL deletion are distinguished based on x's
balance factor, as always:
| | struct pavl_node *x = y->pavl_link[1];
if (x->pavl_balance == -1)
{
<@xref{\NODE\, , Left-side rebalancing case 1 in PAVL deletion.>,541}
}
else
{
<@xref{\NODE\, , Left-side rebalancing case 2 in PAVL deletion.>,542}
}
|
This code is included in @refalso{539
Case 1: x has - balance factor
The same rebalancing is needed here as for a - balance factor in
PAVL insertion, and the same code is used.
| | struct pavl_node *w;
<@xref{\NODE\, , Rebalance for -.> balance factor in PAVL insertion in right subtree,533}
q->pavl_link[dir] = w;
|
This code is included in @refalso{540
Case 2: x has + or 0 balance factor
If x has a + or 0 balance factor, we rotate left at y and update
parent pointers as for any left rotation (see section 15.2 Rotations). We
also update balance factors. If x started with balance factor 0,
then we're done. Otherwise, x becomes the new y for the next loop
iteration, and rebalancing continues. See avldel2, for details on
this rebalancing case.
| | y->pavl_link[1] = x->pavl_link[0];
x->pavl_link[0] = y;
x->pavl_parent = y->pavl_parent;
y->pavl_parent = x;
if (y->pavl_link[1] != NULL)
y->pavl_link[1]->pavl_parent = y;
q->pavl_link[dir] = x;
if (x->pavl_balance == 0)
{
x->pavl_balance = -1;
y->pavl_balance = +1;
break;
}
else
{
x->pavl_balance = y->pavl_balance = 0;
y = x;
}
|
This code is included in @refalso{540
