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


GNU libavl 2.0.1

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

10.3.3 Symmetric Case

 
struct trb_node *y = pa[k - 2]-&#62;trb_link[0];
if (pa[k - 2]-&#62;trb_tag[0] == TRB_CHILD && y-&#62;trb_color == TRB_RED)
  { 
&#60;@xref{\NODE\, , Case 1 in right-side TRB insertion rebalancing.&#62;,346}
} else
{ struct trb_node *x; if (da[k - 1] == 1) y = pa[k - 1]; else
{
&#60;@xref{\NODE\, , Case 3 in right-side TRB insertion rebalancing.&#62;,348}
} &#60;@xref{\NODE\, , Case 2 in right-side TRB insertion rebalancing.&#62;,347} break; }
This code is included in @refalso{340

 
&#60;@xref{\NODE\, , Case 1 in right-side RB insertion rebalancing; rb =>.&#62; trb,207}
This code is included in @refalso{345

 
&#60;@xref{\NODE\, , Case 2 in right-side RB insertion rebalancing; rb =>.&#62; trb,208}
if (y-&#62;trb_tag[0] == TRB_THREAD) 
{ y-&#62;trb_tag[0] = TRB_CHILD; x-&#62;trb_tag[1] = TRB_THREAD; x-&#62;trb_link[1] = y; }
This code is included in @refalso{345

 
&#60;@xref{\NODE\, , Case 3 in right-side RB insertion rebalancing; rb =>.&#62; trb,209}
if (y-&#62;trb_tag[1] == TRB_THREAD) 
{ y-&#62;trb_tag[1] = TRB_CHILD; x-&#62;trb_tag[0] = TRB_THREAD; x-&#62;trb_link[0] = y; }
This code is included in @refalso{345

Exercises:

1. It could be argued that the algorithm here is "impure" because it uses a stack, when elimination of the need for a stack is one of the reasons originally given for using threaded trees. Write a version of trb_probe() that avoids the use of a stack. You can use find_parent() from &#60;@xref{\NODE\, , Find parent of a TBST node.&#62;,327} as a substitute. [answer]


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