7.11.2 From Vine to Balanced Tree |

Transforming a vine into a balanced threaded BST is similar to the same
operation on an unthreaded BST. We can use the same algorithm,
adjusting it for presence of the threads. The following outline is
similar to <BST balance function 88>. In fact, we entirely reuse
<Calculate *leaves* 92>, just changing *bst* to *tbst*. We omit the
final check on the tree's height, because none of the TBST functions are
height-limited.

287. <TBST vine-to-tree function 287> =staticvoidvine_to_tree(structtbst_table*tree)

{unsignedlongvine; /* Number of nodes in main vine. */unsignedlongleaves; /* Nodes in incomplete bottom level, if any. */intheight; /* Height of produced balanced tree. */ <Calculateleaves; bst => tbst 92> <Reduce TBST vine general case to special case 289> <Make special case TBST vine into balanced tree and count height 290> }

This code is included in 284 and 410.

Not many changes are needed to adapt the algorithm to handle threads. Consider the basic right rotation transformation used during a compression:

The rotation does not disturb *a* or *c*, so the only node that can
cause trouble is *b*. If *b* is a real child node, then there's no need
to do anything differently. But if *b* is a thread, then we have to
swap around the direction of the thread, like this:

After a rotation that involves a thread, the next rotation on *B* will
not involve a thread. So after we perform a rotation that adjusts a
thread in one place, the next one in the same place will not require a
thread adjustment.

Every node in the vine we start with has a thread as its right link. This means that during the first pass along the main vine we must perform thread adjustments at every node, but subsequent passes along the vine must not perform any adjustments.

This simple idea is complicated by the initial partial compression pass in trees that do not have exactly one fewer than a power of two nodes. After a partial compression pass, the nodes at the top of the main vine no longer have right threads, but the ones farther down still do.

We deal with this complication by defining the *compress*() function so
it can handle a mixture of rotations with and without right threads.
The rotations that need thread adjustments will always be below the ones
that do not, so this function simply takes a pair of parameters, the
first specifying how many rotations without thread adjustment to
perform, the next how many with thread adjustment. Compare this code
to that for unthreaded BSTs:

288. <TBST vine compression function 288> = /* Performs a nonthreaded compression operationnonthreadtimes, then a threaded compression operationthreadtimes,

starting atroot. */staticvoidcompress(structtbst_node*root,unsignedlongnonthread,unsignedlongthread)

{assert(root!=NULL);while(nonthread--)

{structtbst_node*red=root->tbst_link[0];structtbst_node*black=red->tbst_link[0];root->tbst_link[0] =black;red->tbst_link[0] =black->tbst_link[1];black->tbst_link[1] =red;root=black; }while(thread--)

{structtbst_node*red=root->tbst_link[0];structtbst_node*black=red->tbst_link[0];root->tbst_link[0] =black;red->tbst_link[0] =black;red->tbst_tag[0] =TBST_THREAD;black->tbst_tag[1] =TBST_CHILD;root=black; } }

This code is included in 284.

When we reduce the general case to the 2**n - 1 special case, all of the rotations adjust threads:

289. <Reduce TBST vine general case to special case 289> =compress((structtbst_node*) &tree->tbst_root, 0,leaves);

This code is included in 287.

We deal with the first compression specially, in order to clean up any remaining unadjusted threads:

290. <Make special case TBST vine into balanced tree and count height 290> =vine=tree->tbst_count-leaves;height= 1 + (leaves> 0);if(vine> 1)

{unsignedlongnonleaves=vine/ 2;leaves/= 2;if(leaves>nonleaves)

{leaves=nonleaves;nonleaves= 0; }else

nonleaves-=leaves;compress((structtbst_node*) &tree->tbst_root,leaves,nonleaves);vine/= 2;height++; }

See also 291.

This code is included in 287.

After this, all the remaining compressions use only rotations without thread adjustment, and we're done:

291. <Make special case TBST vine into balanced tree and count height 290> +=while(vine> 1)

{compress((structtbst_node*) &tree->tbst_root,vine/ 2, 0);vine/= 2;height++; }