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


GNU libavl 2.0.1

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

14.7 Balance

We can balance a PBST in the same way that we would balance a BST without parent pointers. In fact, we'll use the same code, with the only change omitting only the maximum height check. This code doesn't set parent pointers, so afterward we traverse the tree to take care of that.

Here are the pieces of the core code that need to be repeated:

 
&#60;@xref{\NODE\, , BST to vine function; bst =>.&#62; pbst,89}
&#60;@xref{\NODE\, , Vine to balanced PBST function.&#62;,512}
&#60;@xref{\NODE\, , Update parent pointers function.&#62;,514}
void 
pbst_balance (struct pbst_table *tree)
{ assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); update_parents (tree); }
This code is included in @refalso{489

 
&#60;@xref{\NODE\, , BST compression function; bst =>.&#62; pbst,95}
static void 
vine_to_tree (struct pbst_table *tree)
{ unsigned long vine; /* Number of nodes in main vine. */ unsigned long leaves; /* Nodes in incomplete bottom level, if any. */ int height; /* Height of produced balanced tree. */ &#60;@xref{\NODE\, , Calculate leaves.&#62;; bst => pbst,91} &#60;@xref{\NODE\, , Reduce vine general case to special case; bst =>.&#62; pbst,92} &#60;@xref{\NODE\, , Make special case vine into balanced tree and count height; bst =>.&#62; pbst,93} }
This code is included in @refalso{511

 
/* Special PBST functions. */
void pbst_balance (struct pbst_table *tree);

Updating Parent Pointers

The procedure for rebalancing a binary tree leaves the nodes' parent pointers pointing every which way. Now we'll fix them. Incidentally, this is a general procedure, so the same code could be used in other situations where we have a tree to which we want to add parent pointers.

The procedure takes the same form as an inorder traversal, except that there is nothing to do in the place where we would normally visit the node. Instead, every time we move down to the left or the right, we set the parent pointer of the node we move to.

The code is straightforward enough. The basic strategy is to always move down to the left when possible; otherwise, move down to the right if possible; otherwise, repeatedly move up until we've moved up to the left to arrive at a node with a right child, then move to that right child.

 
static void 
update_parents (struct pbst_table *tree)
{ struct pbst_node *p; if (tree-&#62;pbst_root == NULL) return; tree-&#62;pbst_root-&#62;pbst_parent = NULL; for (p = tree-&#62;pbst_root; ; p = p-&#62;pbst_link[1])
{ for (; p-&#62;pbst_link[0] != NULL; p = p-&#62;pbst_link[0]) p-&#62;pbst_link[0]-&#62;pbst_parent = p; for (; p-&#62;pbst_link[1] == NULL; p = p-&#62;pbst_parent)
{ for (;;)
{ if (p-&#62;pbst_parent == NULL) return; if (p == p-&#62;pbst_parent-&#62;pbst_link[0]) break; p = p-&#62;pbst_parent; } } p-&#62;pbst_link[1]-&#62;pbst_parent = p; } }
This code is included in @refalso{511

Exercises:

1. There is another approach to updating parent pointers: we can do it during the compressions. Implement this approach. Make sure not to miss any pointers. [answer]


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

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