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(). 

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

This code is included in 253. 

285. <TBST main balance function 285> =
/* 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 284 and 410.