www.delorie.com/gnu/docs/avl/libavl_249.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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-&#62;pavl_balance == -2)
  { 
&#60;@xref{\NODE\, , Rebalance PAVL tree after insertion in left subtree.&#62;,528}
} else if (y-&#62;pavl_balance == +2) {
&#60;@xref{\NODE\, , Rebalance PAVL tree after insertion in right subtree.&#62;,531}
} else
return &n-&#62;pavl_data; if (w-&#62;pavl_parent != NULL) w-&#62;pavl_parent-&#62;pavl_link[y != w-&#62;pavl_parent-&#62;pavl_link[0]] = w; else
tree-&#62;pavl_root = w; return &n-&#62;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-&#62;pavl_link[0];
if (x-&#62;pavl_balance == -1)
  { 
&#60;@xref{\NODE\, , Rebalance for -.&#62; balance factor in PAVL insertion in left subtree,529}
} else
{
&#60;@xref{\NODE\, , Rebalance for +.&#62; 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.

 
&#60;@xref{\NODE\, , Rotate right at y.&#62; in AVL tree; avl => pavl,155}
x-&#62;pavl_parent = y-&#62;pavl_parent;
y-&#62;pavl_parent = x;
if (y-&#62;pavl_link[0] != NULL)
  y-&#62;pavl_link[0]-&#62;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:

avlcase2

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.

 
&#60;@xref{\NODE\, , Rotate left at x.&#62; then right at y in AVL tree; avl => pavl,156}
w-&#62;pavl_parent = y-&#62;pavl_parent;
x-&#62;pavl_parent = y-&#62;pavl_parent = w;
if (x-&#62;pavl_link[1] != NULL)
  x-&#62;pavl_link[1]-&#62;pavl_parent = x;
if (y-&#62;pavl_link[0] != NULL)
  y-&#62;pavl_link[0]-&#62;pavl_parent = y;
This code is included in @refalso{528


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003