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


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.
 
&#60;@xref{\NODE\, , BST to vine function; bst =>.&#62; pbst,89}
&#60;@xref{with parent updates, , Vine to balanced PBST function.&#62;,680}
void 
pbst_balance (struct pbst_table *tree)
{ assert (tree != NULL); tree_to_vine (tree); vine_to_tree (tree); }

 
&#60;@xref{\NODE\, , PBST compression function.&#62;,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. */ &#60;@xref{\NODE\, , Calculate leaves.&#62;; bst => pbst,91} &#60;@xref{\NODE\, , Reduce vine general case to special case; bst =>.&#62; pbst,92} &#60;@xref{\NODE\, , Make special case vine into balanced tree and count height; bst =>.&#62; pbst,93} &#60;@xref{\NODE\, , Set parents of main vine.&#62;,681} }
This code is included in @refalso{679

 
for (q = NULL, p = tree-&#62;pbst_root; p != NULL; q = p, p = p-&#62;pbst_link[0])
  p-&#62;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-&#62;pbst_link[0]; struct pbst_node *black = red-&#62;pbst_link[0]; root-&#62;pbst_link[0] = black; red-&#62;pbst_link[0] = black-&#62;pbst_link[1]; black-&#62;pbst_link[1] = red; red-&#62;pbst_parent = black; if (red-&#62;pbst_link[0] != NULL) red-&#62;pbst_link[0]-&#62;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