4.12.2.3 Implementing Compression [ToC] [Index]     [Skip Back]     [Prev] [Up] [Next]

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.