freebsd rb.h remove を読んでみよう 11

最後のパターンになります。

どうすればいいでしょうか。

黒を増やすためには方法は一つしかありません。

それは赤を黒に変えることです。(*1)

もちろんこれでは左の黒が増えてしまうので
回転させて右にそれを持っていかなくてはなりません。(*2)

これで右の削除されたノードの黒の数は均衡したのですが
その左下のノードの黒の数が増えてしまいます。

しかしこれは簡単に解決できそうです。

多すぎる黒を赤にすればよいでしょう。(*3)

赤に変えてみます 黒の数をチェックしてみましょう。

あっているようですね。

コードを見てみましょう。

/*      ||                                        */\
/*      ||                                        */\
/*    pathp(b)                                    */\
/*   /        \\                                  */\
/* (r)        (b)                                 */\
/*   \                                            */\
/*   (b)                                          */\
/*   /                                            */\
/* (b)                                            */\
assert(leftright != &rbtree->rbt_nil);    \
rbtn_red_set(a_type, a_field, leftright);   \
          //左の子の右の子を赤に変える。(*3)
rbtn_rotate_right(a_type, a_field, pathp->node,tnode);\
          //右に回転させる(*2)
rbtn_black_set(a_type, a_field, tnode);   \
          //回転した後の親ノードを黒にする。(*1)

順番は違いますが同じことをしていますね。

これで赤黒木の削除は終わりです。