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> =
static void 
vine_to_tree (struct tbst_table *tree) 
{
  unsigned long vine;   /* Number of nodes in main vine. */
  unsigned long leaves; /* Nodes in incomplete bottom level, if any. */
  int height;           /* Height of produced balanced tree. */

  <Calculate leaves; 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 operation nonthread times,
   then a threaded compression operation thread times, 
   starting at root. */
static void 
compress (struct tbst_node *root,
          unsigned long nonthread, unsigned long thread) 
{
  assert (root != NULL);

  while (nonthread--) 
    {
      struct tbst_node *red = root->tbst_link[0];
      struct tbst_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--) 
    {
      struct tbst_node *red = root->tbst_link[0];
      struct tbst_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 ((struct tbst_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) 
  {
    unsigned long nonleaves = vine / 2;
    leaves /= 2;
    if (leaves > nonleaves) 
      {
        leaves = nonleaves;
        nonleaves = 0;
      }
    else 
      nonleaves -= leaves;

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

See also 291.

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 ((struct tbst_node *) &tree->tbst_root, vine / 2, 0);
    vine /= 2;
    height++;
  }