6.5.4 Symmetric Case

235. <Right-side rebalancing after RB deletion 235> =
struct rb_node *w = pa[k - 1]->rb_link[0];

if (w->rb_color == RB_RED)
  { 
    <Ensure w is black in right-side RB deletion rebalancing 236> 
  }

if ((w->rb_link[0] == NULL 
     || w->rb_link[0]->rb_color == RB_BLACK)
    && (w->rb_link[1] == NULL 
        || w->rb_link[1]->rb_color == RB_BLACK))
  { <Case 1 in right-side RB deletion rebalancing 237> }
else 
  {
    if (w->rb_link[0] == NULL 
        || w->rb_link[0]->rb_color == RB_BLACK)
      { 
        <Transform right-side RB deletion rebalancing case 3 into case 2 238> 
      }

    <Case 2 in right-side RB deletion rebalancing 239>
    break;
  }

This code is included in 228.

236. <Ensure w is black in right-side RB deletion rebalancing 236> =
w->rb_color = RB_BLACK;
pa[k - 1]->rb_color = RB_RED;

pa[k - 1]->rb_link[0] = w->rb_link[1];
w->rb_link[1] = pa[k - 1];
pa[k - 2]->rb_link[da[k - 2]] = w;

pa[k] = pa[k - 1];
da[k] = 1;
pa[k - 1] = w;
k++;

w = pa[k - 1]->rb_link[0];

This code is included in 235, 366, and 478.

237. <Case 1 in right-side RB deletion rebalancing 237> =
w->rb_color = RB_RED;

This code is included in 235, 367, and 478.

238. <Transform right-side RB deletion rebalancing case 3 into case 2 238> =
struct rb_node *y = w->rb_link[1];
y->rb_color = RB_BLACK;
w->rb_color = RB_RED;
w->rb_link[1] = y->rb_link[0];
y->rb_link[0] = w;
w = pa[k - 1]->rb_link[0] = y;

This code is included in 235, 369, and 482.

239. <Case 2 in right-side RB deletion rebalancing 239> =
w->rb_color = pa[k - 1]->rb_color;
pa[k - 1]->rb_color = RB_BLACK;
w->rb_link[0]->rb_color = RB_BLACK;

pa[k - 1]->rb_link[0] = w->rb_link[1];
w->rb_link[1] = pa[k - 1];
pa[k - 2]->rb_link[da[k - 2]] = w;

This code is included in 235, 368, and 480.