www.delorie.com/gnu/docs/avl/libavl_221.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The rebalancing outline follows <@xref{\NODE\, , \TITLE\}.>{Step 3: Rebalance after RB insertion,201}.
while (k >= 3 && pa[k - 1]->rtrb_color == RTRB_RED) |
The choice of case for insertion on the left side is made in the same way as in <@xref{\NODE\, , Left-side rebalancing after RB insertion.>,202}, except that of course right-side tests for non-empty subtrees are made using rtrb_rtag instead of rtrb_link[1], and similarly for insertion on the right side. In short, we take q (which is not a real variable) as the new node n if this is the first time through the loop, or a node whose color has just been changed to red otherwise. We know that both q and its parent pa[k - 1] are red, violating rule 1 for red-black trees, and that q's grandparent pa[k - 2] is black. Here is the code to distinguish cases:
struct rtrb_node *y = pa[k - 2]->rtrb_link[1]; if (pa[k - 2]->rtrb_rtag == RTRB_CHILD && y->rtrb_color == RTRB_RED) { |
struct rtrb_node *y = pa[k - 2]->rtrb_link[0]; if (pa[k - 2]->rtrb_link[0] != NULL && y->rtrb_color == RTRB_RED) { |
If node q's uncle is red, then no links need be changed. Instead, we will just recolor nodes. We reuse the code for RB insertion (@pageref{rbinscase1}):
<@xref{\NODE\, , Case 1 in left-side RB insertion rebalancing; rb =>.> rtrb,203} |
<@xref{\NODE\, , Case 1 in right-side RB insertion rebalancing; rb =>.> rtrb,207} |
If q is a left child of its parent y and y is a left child of its own parent x, or if both q and y are right children, then we rotate at x away from y. This is the same that we would do in an unthreaded RB tree (@pageref{rbinscase2}).
However, as usual, we must make sure that threads are fixed up properly in the rotation. In particular, for case 2 in left-side rebalancing, we must convert a right thread of y, after rotation, into a null left child pointer of x, like this:
<@xref{\NODE\, , Case 2 in left-side RB insertion rebalancing; rb =>.> rtrb,204} if (y->rtrb_rtag == RTRB_THREAD) |
For the right-side rebalancing case, we must convert a null left child of y, after rotation, into a right thread of x:
<@xref{\NODE\, , Case 2 in right-side RB insertion rebalancing; rb =>.> rtrb,208} if (x->rtrb_link[1] == NULL) |
If q is a left child and its parent is a right child, or vice versa, then we have an instance of case 3, and we rotate at q's parent in the direction from q to its parent. We handle this case as seen before for unthreaded RB trees (@pageref{rbinscase3}), with the addition of fix-ups for threads during rotation.
The left-side fix-up and the code to do it look like this:
<@xref{\NODE\, , Case 3 in left-side RB insertion rebalancing; rb =>.> rtrb,205} if (x->rtrb_link[1] == NULL) |
Here's the right-side fix-up and code:
<@xref{\NODE\, , Case 3 in right-side RB insertion rebalancing; rb =>.> rtrb,209} if (y->rtrb_rtag == RTRB_THREAD) |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |