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

search

	Buy GNU books!

GNU libavl 2.0.1

10.3.2 Step 3: Rebalance

The basic rebalancing loop is unchanged from <@xref{\NODE\, , \TITLE\}.>{Step 3: Rebalance after RB insertion,201}.

while (k >= 3 && pa[k - 1]->trb_color == TRB_RED) { if (da[k - 2] == 0) { <@xref{\NODE\, , Left-side rebalancing after TRB insertion.>,341} } else { <@xref{\NODE\, , Right-side rebalancing after TRB insertion.>,345} } } tree->trb_root->trb_color = TRB_BLACK;

This code is included in @refalso{337

The cases for rebalancing are the same as in <@xref{\NODE\, , \TITLE\}.>{Left-side rebalancing after RB insertion,202}, too. We do need to check for threads, instead of null pointers.

struct trb_node *y = pa[k - 2]->trb_link[1]; if (pa[k - 2]->trb_tag[1] == TRB_CHILD && y->trb_color == TRB_RED) { <@xref{\NODE\, , Case 1 in left-side TRB insertion rebalancing.>,342} } else { struct trb_node *x; if (da[k - 1] == 0) y = pa[k - 1]; else { <@xref{\NODE\, , Case 3 in left-side TRB insertion rebalancing.>,344} } <@xref{\NODE\, , Case 2 in left-side TRB insertion rebalancing.>,343} break; }

This code is included in @refalso{340

The rest of this section deals with the individual rebalancing cases, the same as in unthreaded RB insertion (see section 7.4.3 Step 3: Rebalance). Each iteration deals with a node whose color has just been changed to red, which is the newly inserted node n in the first trip through the loop. In the discussion, we'll call this node q.

Case 1: q's uncle is red

If node q has an red "uncle", then only recoloring is required. Because no links are changed, no threads need to be updated, and we can reuse the code for RB insertion without change:

<@xref{\NODE\, , Case 1 in left-side RB insertion rebalancing; rb =>.> trb,203}

This code is included in @refalso{341

Case 2: q is the left child of its parent

If q is the left child of its parent, we rotate right at q's grandparent, and recolor a few nodes. Here's the transformation:

This transformation can only cause thread problems with subtree c, since the other subtrees stay firmly in place. If c is a thread, then we need to make adjustments after the transformation to account for the difference between threaded and unthreaded rotation, so that the final operation looks like this:

<@xref{\NODE\, , Case 2 in left-side RB insertion rebalancing; rb =>.> trb,204} if (y->trb_tag[1] == TRB_THREAD) { y->trb_tag[1] = TRB_CHILD; x->trb_tag[0] = TRB_THREAD; x->trb_link[0] = y; }

This code is included in @refalso{341

Case 3: q is the right child of its parent

The modification to case 3 is the same as the modification to case 2, but it applies to a left rotation instead of a right rotation. The adjusted case looks like this:

<@xref{\NODE\, , Case 3 in left-side RB insertion rebalancing; rb =>.> trb,205} if (y->trb_tag[0] == TRB_THREAD) { y->trb_tag[0] = TRB_CHILD; x->trb_tag[1] = TRB_THREAD; x->trb_link[1] = y; }

This code is included in @refalso{341