freebsd rb.h remove を読んでみよう 10
親が黒でその子が赤の場合を見てみましょう。これが最後のパターンになります。
このパターンは更にひ孫に赤があるかどうかで場合分けできます。
９番のひ孫に赤があるパターンから見ていきましょう。
まず最初に気になることは子が赤でひ孫が赤のパターンはこれだけではないのではないかということです。
こういうパターンはどうでしょうか。
赤の位置も左だけ、赤が2個続くこともないのでこのパターンはありえます。
しかし少し考えてみましょう。
矢印の部分のはてなのノードは黒でないことはできません。
なぜならばもしここにノードがないならばこのレベルで左の 黒に対して不均衡が生じてしまうからです。
これは削除をする前に解決されていなければいけないので おかしいということになります。
よってこのノードは黒になります。 するとどうでしょう。
結局この黒の更に子ノードが黒か赤かで場合分けされるので ９か１０かのパターンと同じになってしまいます。
つまりこのパターンは９、１０のパターンに吸収されてしまうということです。
では９のパターンから見ていきましょう。
パッと見た感じ左の赤を右に回すと右の黒が増えて解決しそうです。
右に回してみました。 しかし右の黒は増えません。
逆に左の黒が一つ減ってしまいました。
この減った黒を増やすにはどうすればいいでしょうか。
答えは一つしかありません。それは赤を黒に変えるです。
上の赤を黒にしてみましょうか。
下の二つのノードで黒が一つ多くなってしまいます。
これを解決することはできそうにありません。
右に回してみても右側で黒が一つ多いままです。
黒を赤にすることもできません。
よってこの方法はだめそうです。
上の赤を黒にしてみましょうか。
そしてこの増えた黒を右に送りましょう。
左に黒が一つ増えれば解決しそうです。
左に回転させればよさそうですね。
すべての枝で黒の数が合いました。
コードで見てみましょう。
if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (r) (b) */\
/* \ */\
/* (b) */\
/* / */\
/* (r) */\
a_type *unode;││ │ │ │ \
rbtn_black_set(a_type, a_field, leftrightleft);│ \
//左の右の左の子を黒にする。
rbtn_rotate_right(a_type, a_field, pathp->node,unode);\
//全体を右に回転する。新たなルートノードをunodeに入れる。
rbtn_rotate_right(a_type, a_field, pathp->node,tnode);\
//右に回転した元のルート(pathp->node)を中心に右に回転。新たなルートノードをtnodeに入れる。
rbtn_right_set(a_type, a_field, unode, tnode);│\
//unodeの右にtnodeをセット。
rbtn_rotate_left(a_type, a_field, unode, tnode);\
//unodeを中心に左に回転
}
コードが少しややこしいですね。
まずは左の右の左の子を黒にする。のところです。ここは簡単でしょう。
次からは回転したルートの新旧のポインターがどこを指しているかに注意が必要です。 pathpを中心に右に回転したところです。 新たなルートはunodeに入れられています。
もう一度pathpを中心に右回転します。
そしてその時のルートノードをtnodeにセットします。
そしてunodeとtnodeを結んでいます。
最後はルートであるunodeを中心に左に回転させます。
これで黒の数が均衡しました。 次回はパターン１０を見てみましょう。
