GNU libavl 2.0.1
15.4.3 Step 4: Rebalance
The changes needed to the rebalancing code for parent pointers
resemble the changes for threads in that we can reuse most of the code
from plain AVL trees. We just need to add a few new statements to
each rebalancing case to adjust the parent pointers of nodes whose
parents have changed.
The outline of the rebalancing code should be familiar by now. The
code to update the link to the root of the rebalanced subtree is the
only change. It needs a special case for the root, because the parent
pointer of the root node is a null pointer, not the pseudo-root node.
The other choice would simplify this piece of code, but complicate
other pieces (see section 14.1 Data Types).
| | if (y->pavl_balance == -2)
{
<@xref{\NODE\, , Rebalance PAVL tree after insertion in left subtree.>,528}
}
else if (y->pavl_balance == +2)
{
<@xref{\NODE\, , Rebalance PAVL tree after insertion in right subtree.>,531}
}
else
return &n->pavl_data;
if (w->pavl_parent != NULL)
w->pavl_parent->pavl_link[y != w->pavl_parent->pavl_link[0]] = w;
else
tree->pavl_root = w;
return &n->pavl_data;
|
This code is included in @refalso{523
As usual, the cases for rebalancing are distinguished based on the
balance factor of the child of the unbalanced node on its taller side:
| | struct pavl_node *x = y->pavl_link[0];
if (x->pavl_balance == -1)
{
<@xref{\NODE\, , Rebalance for -.> balance factor in PAVL insertion in left subtree,529}
}
else
{
<@xref{\NODE\, , Rebalance for +.> balance factor in PAVL insertion in left subtree,530}
}
|
This code is included in @refalso{527
Case 1: x has - balance factor
The added code here is exactly the same as that added to BST rotation
to handle parent pointers (in Exercise 14.2-1), and for good reason
since this case simply performs a right rotation in the PAVL tree.
| | <@xref{\NODE\, , Rotate right at y.> in AVL tree; avl => pavl,155}
x->pavl_parent = y->pavl_parent;
y->pavl_parent = x;
if (y->pavl_link[0] != NULL)
y->pavl_link[0]->pavl_parent = y;
|
This code is included in @refalso{528
Case 2: x has + balance factor
When x has a + balance factor, we need a double rotation, composed
of a right rotation at x followed by a left rotation at y. The
diagram below show the effect of each of the rotations:
Along with this double rotation comes a small bulk discount in parent
pointer assignments. The parent of w changes in both rotations, but
we only need assign to it its final value once, ignoring the
intermediate value.
| | <@xref{\NODE\, , Rotate left at x.> then right at y in AVL tree; avl => pavl,156}
w->pavl_parent = y->pavl_parent;
x->pavl_parent = y->pavl_parent = w;
if (x->pavl_link[1] != NULL)
x->pavl_link[1]->pavl_parent = x;
if (y->pavl_link[0] != NULL)
y->pavl_link[0]->pavl_parent = y;
|
This code is included in @refalso{528
