4.12.2.3 Implementing Compression

The final bit of code we need is that for performing a compression. The following code performs a compression consisting of count applications of the compression transformation starting at root:

95. <BST compression function 95> =
/* Performs a compression transformation count times, 
   starting at root. */
static void 
compress (struct bst_node *root, unsigned long count) 
{
  assert (root != NULL);

  while (count–) 
    {
      struct bst_node *red = root->bst_link[0];
      struct bst_node *black = red->bst_link[0];

      root->bst_link[0] = black;
      red->bst_link[0] = black->bst_link[1];
      black->bst_link[1] = red;
      root = black;
    }
}

This code is included in 90 and 512.

The operation of compress() should be obvious, given the discussion earlier. See Balancing General Trees, above, for a review.

See also:  [Stout 1986], vine_to_tree procedure.