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

search

	Buy GNU books!

GNU libavl 2.0.1

7.4.5.1 Symmetric Case

struct rb_node *y = pa[k - 2]->rb_link[0]; if (y != NULL && y->rb_color == RB_RED) { <@xref{\NODE\, , Case 1 in right-side initial-black RB insertion rebalancing.>,217} } else { struct rb_node *x; if (da[k - 1] == 1) y = pa[k - 1]; else { <@xref{\NODE\, , Case 3 in right-side initial-black RB insertion rebalancing.>,219} } <@xref{\NODE\, , Case 2 in right-side initial-black RB insertion rebalancing.>,218} }

This code is included in @refalso{211

<@xref{\NODE\, , Case 1 in left-side initial-black RB insertion rebalancing.>,213}

This code is included in @refalso{216

x = pa[k - 2]; x->rb_color = q->rb_color = RB_RED; y->rb_color = RB_BLACK; x->rb_link[1] = y->rb_link[0]; y->rb_link[0] = x; pa[k - 3]->rb_link[da[k - 3]] = y; break;

This code is included in @refalso{216

x = pa[k - 1]; y = pa[k - 2]->rb_link[1] = q; x->rb_link[0] = y->rb_link[1]; q = y->rb_link[1] = x;

This code is included in @refalso{216