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.

```527. <Step 4: Rebalance after PAVL insertion 527> =
if (y->pavl_balance == -2)
{     <Rebalance PAVL tree after insertion in left subtree 528>   }
else if (y->pavl_balance == +2)
{     <Rebalance PAVL tree after insertion in right subtree 531>   }
else   return &n->pavl_data;
if (w->pavl_parent != NULL)
else   tree->pavl_root = w;

return &n->pavl_data;
```

This code is included in 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:

```528. <Rebalance PAVL tree after insertion in left subtree 528> =
if (x->pavl_balance == -1)
{     <Rebalance for - balance factor in PAVL insertion in left subtree 529>   }
else   {     <Rebalance for + balance factor in PAVL insertion in left subtree 530>   }
```

This code is included in 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.

```529. <Rebalance for - balance factor in PAVL insertion in left subtree 529> =
<Rotate right at y in AVL tree; avl => pavl 155>
x->pavl_parent = y->pavl_parent;
y->pavl_parent = x;
```

This code is included in 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.

```530. <Rebalance for + balance factor in PAVL insertion in left subtree 530> =
<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;