GNU libavl 2.0.1
10.4.3 Step 3: Rebalance
The outline for rebalancing after threaded RB deletion is the same as
for the unthreaded case (see section 7.5.2 Step 3: Rebalance):
| | if (p->trb_color == TRB_BLACK)
{
for (; k > 1; k--)
{
if (pa[k - 1]->trb_tag[da[k - 1]] == TRB_CHILD)
{
struct trb_node *x = pa[k - 1]->trb_link[da[k - 1]];
if (x->trb_color == TRB_RED)
{
x->trb_color = TRB_BLACK;
break;
}
}
if (da[k - 1] == 0)
{
<@xref{\NODE\, , Left-side rebalancing after TRB deletion.>,357}
}
else
{
<@xref{\NODE\, , Right-side rebalancing after TRB deletion.>,363}
}
}
if (tree->trb_root != NULL)
tree->trb_root->trb_color = TRB_BLACK;
}
|
This code is included in @refalso{349
The rebalancing cases are the same, too. We need to check for thread
tags, not for null pointers, though, in some places:
| | struct trb_node *w = pa[k - 1]->trb_link[1];
if (w->trb_color == TRB_RED)
{
<@xref{\NODE\, , Ensure w.> is black in left-side TRB deletion rebalancing,358}
}
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 left-side TRB deletion rebalancing.>,359}
}
else
{
if (w->trb_tag[1] == TRB_THREAD
|| w->trb_link[1]->trb_color == TRB_BLACK)
{
<@xref{\NODE\, , Transform left-side TRB deletion rebalancing case 3 into case 2.>,361}
}
<@xref{\NODE\, , Case 2 in left-side TRB deletion rebalancing.>,360}
break;
}
|
This code is included in @refalso{356
Case Reduction: Ensure w is black
This transformation does not move around any subtrees that might be
threads, so there is no need for it to change.
| | <@xref{\NODE\, , Ensure w.> is black in left-side RB deletion rebalancing; rb => trb,228}
|
This code is included in @refalso{357
Case 1: w has no red children
This transformation just recolors nodes, so it also does not need any
changes.
| | <@xref{\NODE\, , Case 1 in left-side RB deletion rebalancing; rb =>.> trb,229}
|
This code is included in @refalso{357
Case 2: w's right child is red
If w has a red right child and a left thread, then it is necessary to
adjust tags and links after the left rotation at w and recoloring, as
shown in this diagram:
| | <@xref{\NODE\, , Case 2 in left-side RB deletion rebalancing; rb =>.> trb,230}
if (w->trb_tag[0] == TRB_THREAD)
{
w->trb_tag[0] = TRB_CHILD;
pa[k - 1]->trb_tag[1] = TRB_THREAD;
pa[k - 1]->trb_link[1] = w;
}
|
This code is included in @refalso{357
Case 3: w's left child is red
If w has a red left child, which has a right thread, then we again need
to adjust tags and links after right rotation at w and recoloring, as
shown here:
| | <@xref{\NODE\, , Transform left-side RB deletion rebalancing case 3 into case 2; rb =>.> trb,231}
if (w->trb_tag[1] == TRB_THREAD)
{
w->trb_tag[1] = TRB_CHILD;
w->trb_link[1]->trb_tag[0] = TRB_THREAD;
w->trb_link[1]->trb_link[0] = w;
}
|
This code is included in @refalso{357
