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

search

	Buy GNU books!

GNU libavl 2.0.1

5.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:

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

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

See also: [ Stout 1986], vine_to_tree procedure.