left-leaning 赤黒木(red-black tree) - ノードの削除(削除ノードの補充)

まず、あるノード◎^a をリストから取り除く場合を考えてみる。

◎^aが末端の赤ノードなら left-leaning 赤黒木の 6つの条件をどれも崩さないで取り除けるけれど(下の図)

そうでない場合はその取り除かれた場所にどこからかノードを見繕って補充することが必要になってしまう。

二分探索木の場合はノードの補充を次のどちらかで行えるけれど、left-leaning 赤黒木の場合は 2. の方が平衡を取り戻すために必要な操作の数が少そうなので 2. で行ってみる。

1. 削除するノード ◎^a の左の子の部分木の中から最も大きな値のノードを補充に使う。
2. 削除するノード ◎^a の右の子の部分木の中から最も小さな値のノードを補充に使う。

もちろん赤黒木なので ◎^a の色は赤のときと黒のときがあるけれど、赤ノード○^a を取り除くときは ◎^z の色を赤で補充すればよいし、黒ノード●^a を取り除くときは ◎^z の色を黒で補充できる。

また、補充を済ませた木の形(下図の左側)は、取り除かれるノードが末端のときの木(下図の右側)とおなじ形になるので、あとは、末端のノードが取り除かれたときについて考えれば良いことになる。