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


GNU libavl 2.0.1

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

11.9 Balance

As for so many other operations, we can reuse most of the TBST balancing code to rebalance RTBSTs. Some of the helper functions can be completely recycled:

 
&#60;@xref{\NODE\, , RTBST tree-to-vine function.&#62;,409}
&#60;@xref{\NODE\, , RTBST vine compression function.&#62;,410}
&#60;@xref{\NODE\, , TBST vine-to-tree function; tbst =>.&#62; rtbst,285}
&#60;@xref{\NODE\, , TBST main balance function; tbst =>.&#62; rtbst,283}
This code is included in @refalso{375

The only substantative difference for the remaining two functions is that there is no need to set nodes' left tags (since they don't have any):

 
static void 
tree_to_vine (struct rtbst_table *tree)
{ struct rtbst_node *p; if (tree-&#62;rtbst_root == NULL) return; p = tree-&#62;rtbst_root; while (p-&#62;rtbst_link[0] != NULL) p = p-&#62;rtbst_link[0]; for (;;)
{ struct rtbst_node *q = p-&#62;rtbst_link[1]; if (p-&#62;rtbst_rtag == RTBST_CHILD)
{ while (q-&#62;rtbst_link[0] != NULL) q = q-&#62;rtbst_link[0]; p-&#62;rtbst_rtag = RTBST_THREAD; p-&#62;rtbst_link[1] = q; } if (q == NULL) break; q-&#62;rtbst_link[0] = p; p = q; } tree-&#62;rtbst_root = p; }
This code is included in @refalso{408

 
/* Performs a compression transformation count times, 
starting at root. */ static void
compress (struct rtbst_node *root, unsigned long nonthread, unsigned long thread)
{ assert (root != NULL); while (nonthread--)
{ struct rtbst_node *red = root-&#62;rtbst_link[0]; struct rtbst_node *black = red-&#62;rtbst_link[0]; root-&#62;rtbst_link[0] = black; red-&#62;rtbst_link[0] = black-&#62;rtbst_link[1]; black-&#62;rtbst_link[1] = red; root = black; } while (thread--)
{ struct rtbst_node *red = root-&#62;rtbst_link[0]; struct rtbst_node *black = red-&#62;rtbst_link[0]; root-&#62;rtbst_link[0] = black; red-&#62;rtbst_link[0] = NULL; black-&#62;rtbst_rtag = RTBST_CHILD; root = black; } }
This code is included in @refalso{408


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

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