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

GNU libavl 2.0.1

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

8.11 Balance

Just like their unthreaded cousins, threaded binary trees can become degenerate, leaving their good performance characteristics behind. When this happened in a unthreaded BST, stack overflow often made it necessary to rebalance the tree. This doesn't happen in our implementation of threaded BSTs, because none of the routines uses a stack. It is still useful to have a rebalance routine for performance reasons, so we will implement one, in this section, anyway.

There is no need to change the basic algorithm. As before, we convert the tree to a linear "vine", then the vine to a balanced binary search tree. See section 5.12 Balance, for a review of the balancing algorithm.

Here is the outline and prototype for tbst_balance().

&#60;@xref{\NODE\, , TBST tree-to-vine function.&#62;,284}
&#60;@xref{\NODE\, , TBST vine compression function.&#62;,286}
&#60;@xref{\NODE\, , TBST vine-to-tree function.&#62;,285}
&#60;@xref{\NODE\, , TBST main balance function.&#62;,283}
This code is included in @refalso{251

/* Balances tree. */
tbst_balance (struct tbst_table *tree)
{ assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); }
This code is included in @refalso{282

8.11.1 From Tree to Vine  
8.11.2 From Vine to Balanced Tree  

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