7.11 Balance [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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 Balancing a BST, for a review of the balancing algorithm.

Here is the outline and prototype for tbst_balance(). 

282. <TBST balance function 282> =
<TBST tree-to-vine function 284>
<TBST vine compression function 286>
<TBST vine-to-tree function 285>
<TBST main balance function 283>

This code is included in 251. 

283. <TBST main balance function 283> =
/* Balances tree. */
void 
tbst_balance (struct tbst_table *tree) 
{
  assert (tree != NULL);

  tree_to_vine (tree);
  vine_to_tree (tree);
}

This code is included in 282 and 408.