www.delorie.com/gnu/docs/avl/libavl_148.html

search

	Buy GNU books!

GNU libavl 2.0.1

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

<@xref{\NODE\, , TBST tree-to-vine function.>,284} <@xref{\NODE\, , TBST vine compression function.>,286} <@xref{\NODE\, , TBST vine-to-tree function.>,285} <@xref{\NODE\, , TBST main balance function.>,283}

This code is included in @refalso{251

/* 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 @refalso{282

8.11.1 From Tree to Vine
8.11.2 From Vine to Balanced Tree