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


GNU libavl 2.0.1

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

10.4.5 Symmetric Case

 
struct trb_node *w = pa[k - 1]-&#62;trb_link[0];
if (w-&#62;trb_color == TRB_RED) 
  { 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in right-side TRB deletion rebalancing,364}
} if ((w-&#62;trb_tag[0] == TRB_THREAD
|| w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK) && (w-&#62;trb_tag[1] == TRB_THREAD
|| w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK)) {
&#60;@xref{\NODE\, , Case 1 in right-side TRB deletion rebalancing.&#62;,365}
} else
{ if (w-&#62;trb_tag[0] == TRB_THREAD
|| w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK) {
&#60;@xref{\NODE\, , Transform right-side TRB deletion rebalancing case 3 into case 2.&#62;,367}
} &#60;@xref{\NODE\, , Case 2 in right-side TRB deletion rebalancing.&#62;,366} break; }
This code is included in @refalso{356

 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in right-side RB deletion rebalancing; rb => trb,234}
This code is included in @refalso{363

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

 
&#60;@xref{\NODE\, , Case 2 in right-side RB deletion rebalancing; rb =>.&#62; trb,237}
if (w-&#62;trb_tag[1] == TRB_THREAD) 
{ w-&#62;trb_tag[1] = TRB_CHILD; pa[k - 1]-&#62;trb_tag[0] = TRB_THREAD; pa[k - 1]-&#62;trb_link[0] = w; }
This code is included in @refalso{363

 
&#60;@xref{\NODE\, , Transform right-side RB deletion rebalancing case 3 into case 2; rb =>.&#62; trb,236}
if (w-&#62;trb_tag[0] == TRB_THREAD) 
{ w-&#62;trb_tag[0] = TRB_CHILD; w-&#62;trb_link[0]-&#62;trb_tag[1] = TRB_THREAD; w-&#62;trb_link[0]-&#62;trb_link[1] = w; }
This code is included in @refalso{363

Exercises:

1. Write another version of trb_delete() that does not use a stack. You can use &#60;@xref{\NODE\, , Find parent of a TBST node.&#62;,327} to find the parent of a node. [answer]


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