www.delorie.com/gnu/docs/avl/libavl_288.html search
GNU libavl 2.0.1

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

## Chapter 13

### Section 13.4

1. No. It would work, except for the important special case where q is the pseudo-root but p-&#62;pbst_parent is NULL.

### Section 13.7

1.
 ```<@xref{\NODE\, , BST to vine function; bst =>.> pbst,89} <@xref{with parent updates, , Vine to balanced PBST function.>,680} void pbst_balance (struct pbst_table *tree) { assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); } ```

 ```<@xref{\NODE\, , PBST compression function.>,682} static void vine_to_tree (struct pbst_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. */ struct pbst_node *p, *q; /* Current visited node and its parent. */ <@xref{\NODE\, , Calculate leaves.>; bst => pbst,91} <@xref{\NODE\, , Reduce vine general case to special case; bst =>.> pbst,92} <@xref{\NODE\, , Make special case vine into balanced tree and count height; bst =>.> pbst,93} <@xref{\NODE\, , Set parents of main vine.>,681} } ```
This code is included in @refalso{679

 ```for (q = NULL, p = tree->pbst_root; p != NULL; q = p, p = p->pbst_link[0]) p->pbst_parent = q; ```
This code is included in @refalso{680

 ```static void compress (struct pbst_node *root, unsigned long count) { assert (root != NULL); while (count--) { struct pbst_node *red = root->pbst_link[0]; struct pbst_node *black = red->pbst_link[0]; root->pbst_link[0] = black; red->pbst_link[0] = black->pbst_link[1]; black->pbst_link[1] = red; red->pbst_parent = black; if (red->pbst_link[0] != NULL) red->pbst_link[0]->pbst_parent = red; root = black; } } ```
This code is included in @refalso{680

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

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