www.delorie.com/gnu/docs/avl/libavl_75.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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-&#62;bst_link[0]; struct bst_node *black = red-&#62;bst_link[0]; root-&#62;bst_link[0] = black; red-&#62;bst_link[0] = black-&#62;bst_link[1]; black-&#62;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.


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003