GNU libavl 2.0.1
Chapter 14
Section 14.2
1.
| | static void
rotate_right (struct pbst_node **yp)
{
struct pbst_node *y = *yp;
struct pbst_node *x = y->pbst_link[0];
y->pbst_link[0] = x->pbst_link[1];
x->pbst_link[1] = y;
*yp = x;
x->pbst_parent = y->pbst_parent;
y->pbst_parent = x;
if (y->pbst_link[0] != NULL)
y->pbst_link[0]->pbst_parent = y;
}
|
| | static void
rotate_left (struct pbst_node **xp)
{
struct pbst_node *x = *xp;
struct pbst_node *y = x->pbst_link[1];
x->pbst_link[1] = y->pbst_link[0];
y->pbst_link[0] = x;
*xp = y;
y->pbst_parent = x->pbst_parent;
x->pbst_parent = y;
if (x->pbst_link[1] != NULL)
x->pbst_link[1]->pbst_parent = x;
}
|
Section 14.4.2
1.
Yes. Both code segments update the nodes along the direct path from
y down to n, including node y but not node n. The plain AVL
code excluded node n by updating nodes as it moved down to them and
making arrival at node n the loop's termination condition. The PAVL
code excludes node n by starting at it but updating the parent of
each visited node instead of the node itself.
There still could be a problem at the edge case where no nodes'
balance factors were to be updated, but there is no such case. There
is always at least one balance factor to update, because every
inserted node has a parent whose balance factor is affected by its
insertion. The one exception would be the first node inserted into an
empty tree, but that was already handled as a special case.
2.
Sure. There is no parallel to Exercise 5.4.4-4 because q is never
the pseudo-root.
