トップ > code reading > freebsd rb.h insert を読んでみよう2

freebsd rb.h insert を読んでみよう2

code reading red black tree

前回は左に赤が二つつながる場合を見ました。

http://yamshing.hatenablog.com/entry/2015/09/30/205603

今回は右に赤が来る場合です。

では読んでみましょう。

    a_type *right = pathp[1].node;     //次のノードを
 rbtn_right_set(a_type, a_field, cnode, right); //右にセット
 if (rbtn_red_get(a_type, a_field, right)) {    //そのノードが赤なら
 a_type *left = rbtn_left_get(a_type, a_field, cnode);   //そしてその左が

 if (rbtn_red_get(a_type, a_field, left)) {        //赤なら
            /* Split 4-node. */                    \
            rbtn_black_set(a_type, a_field, left);        //左を黒
            rbtn_black_set(a_type, a_field, right);        //右を黒に
            rbtn_red_set(a_type, a_field, cnode);        //親を赤にします

 

つまり

　　黒

赤　　　赤

なら

　　赤

黒　　　黒

にするということですね。

    } else {                        //左が赤でないなら（黒か無しなら）
      /* Lean left. */                    \
      a_type *tnode;                    \
      bool tred = rbtn_red_get(a_type, a_field, cnode);    //親の色を覚えて
      rbtn_rotate_left(a_type, a_field, cnode, tnode);    //左回りで新しい親をtnodeへ
      rbtn_color_set(a_type, a_field, tnode, tred);    //その新しい親を前の親の色に塗ります
      rbtn_red_set(a_type, a_field, cnode);       //前の親は赤に
      cnode = tnode;                    //前の親を今の親に変更
 }

 ここは

　　黒/赤

黒/無　　赤

という状態です。

親の色を覚えておいて左回り

 

 　　赤

　黒/赤

黒/無

 

覚えておいた色を前の親にそして前の親を赤にします。

 

　　　黒/赤

　　赤

黒/無

 

そして最後に

    rbtree->rbt_root = path->node;          //今の親をルートに
    rbtn_black_set(a_type, a_field, rbtree->rbt_root);  //ルートを黒にします。

以上が挿入です。

まとめてみると

 

左に赤が２つ連続する

左と右が赤

左が赤以外右に赤が２つ連続する

左が赤以外黒赤となる

 

４つのパターンがありそうです。

左が赤以外右に赤が２つ連続するパターンは

左に回転すると左に赤が２つ連続するパターンになるので

３つのパターンでしょうか。

次回はちょっと複雑になる削除を見ていきましょう。