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

削除を見ていきましょう。
赤ノードの削除は何も変わらないので無視できます。
削除されるのが黒ノードの場合
削除された黒ノードを補うために赤ノードを黒に変えていきます。
そうなのでその変える赤の位置で場合分けしていきます。
では見てみましょう。

親が赤の場合
子に黒が消されたのでその反対側の子が無しはありえない状況です。

ここで(？)はノードなしです。

この木はありえません。

よって赤が親の場合は子が黒になります。

親の赤を黒にすることによって次の赤に影響が出る場合があるので(赤赤になったり赤が右に来る場合)
子に赤があるかないかで場合分けします。

(？)はノードなしか黒です。

この四つが赤が親の時の全パターンです。

次は黒が親の場合を見てみましょう。

親が黒の場合は赤があるかないかで大きく二つに分かれます。
赤がある場合はその位置によって場合わけしていきます。

その時右に赤が来ないというfreebsdの実装に注意します。

(？)はノードなしか黒です。

まとめると

　赤がない場合(5,8)

　孫が赤の場合(6,7)

　子が赤の場合(9, 10)

となります。

ここで9の場合子の赤の左に黒赤とノードが繋がる場合がありそうです。

この場合はどうなのでしょう。

一つ目の子の赤の右にノードが無いということは黒の数が不均衡になるので
ありえません。するとこの赤ノードの子は赤ではありえないので黒になります。

そのためこの木は結局9か10と同じになるので場合わけする必要はありません。

次はこれらの場合どのように赤と黒の均衡を取り戻すのか

rb.hの実装を見ていきましょう。