14.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 PBST Data Types).

529. <Step 4: Rebalance after PAVL insertion 529> =
if (y->pavl_balance == -2)
  { 
    <Rebalance PAVL tree after insertion in left subtree 530> 
  }
else if (y->pavl_balance == +2)
  { 
    <Rebalance PAVL tree after insertion in right subtree 533> 
  }
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 525.

As usual, the cases for rebalancing are distinguished based on the balance factor of the child of the unbalanced node on its taller side:

530. <Rebalance PAVL tree after insertion in left subtree 530> =
struct pavl_node *x = y->pavl_link[0];
if (x->pavl_balance == -1)
  { 
    <Rebalance for - balance factor in PAVL insertion in left subtree 531> 
  } 
else 
  { 
    <Rebalance for + balance factor in PAVL insertion in left subtree 532> 
  }

This code is included in 529.

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.

531. <Rebalance for - balance factor in PAVL insertion in left subtree 531> =
<Rotate right at y in AVL tree; avl => pavl 157>
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 530.

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.

532. <Rebalance for + balance factor in PAVL insertion in left subtree 532> =
<Rotate left at x then right at y in AVL tree; avl => pavl 158>
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 530 and 546.