www.delorie.com/gnu/docs/avl/libavl_181.html

search

	Buy GNU books!

GNU libavl 2.0.1

10.4.5 Symmetric Case

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

This code is included in @refalso{356

<@xref{\NODE\, , Ensure w.> is black in right-side RB deletion rebalancing; rb => trb,234}

This code is included in @refalso{363

<@xref{\NODE\, , Case 1 in right-side RB deletion rebalancing; rb =>.> trb,235}

This code is included in @refalso{363

<@xref{\NODE\, , Case 2 in right-side RB deletion rebalancing; rb =>.> trb,237} if (w->trb_tag[1] == TRB_THREAD) { w->trb_tag[1] = TRB_CHILD; pa[k - 1]->trb_tag[0] = TRB_THREAD; pa[k - 1]->trb_link[0] = w; }

This code is included in @refalso{363

<@xref{\NODE\, , Transform right-side RB deletion rebalancing case 3 into case 2; rb =>.> trb,236} if (w->trb_tag[0] == TRB_THREAD) { w->trb_tag[0] = TRB_CHILD; w->trb_link[0]->trb_tag[1] = TRB_THREAD; w->trb_link[0]->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 <@xref{\NODE\, , Find parent of a TBST node.>,327} to find the parent of a node. [answer]