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

赤ノード ○^z の右の黒ノード ●^a を取り除く場合を考えてみる。

●^a を取り除くと ○^z の右側は、葉から根までの黒ノードの数が他の葉より一つ少なくなって平衡が崩れてしまう。この黒ノードが一つ少ない葉を ■^-1 で表す。

ひとまず ○^z の右と左で平衡を取り戻すために ●^y の色を赤に変えてみる。すると ○^z の左側の葉から根までの黒ノードの数が一つ減って ○^y-1 となる。○^z の左と右のどちらも葉から根までの黒ノードの数がその他より一つ少いので、左右の -1 を取り除いて ○^z-1 と描ける。

このとき ○^z-1 と ○^y は (赤)左(赤)の状態にあるので、「ノードの追加(赤ノードの左)」と同様に操作してみる。
赤ノード ○^z-1 は黒ノードの左ノードのはず。

この回転の前と後で ○^z-1 の右左の葉から根までの黒ノードの数の影響を考えてみる。

• ○^z-1 の右は、親の黒ノードが一つ減って右に追加されたので±0
• ○^z-1 の左は、親の黒ノードが一つ減って、赤ノード○^y の色が黒になったので±0

つまり、この回転の前と後では葉から根までの黒ノードの数に影響はないことがわかる。(影響があったら赤黒木の回転にならないから考えるまでもないけれど)

赤ノード ○^z-1 は葉から根までの黒ノードの数が他よりも一つ少いことを除くと、6つの left-leaning 赤黒木の全ての条件を満たしている。この ○^z-1 の状態をここでは (赤)頭^-1 状態と呼ぶことにする。

(赤)頭^-1 は、その赤ノードの色を黒へ変えると葉から根までの黒ノードの数が一つ増えて -1 が解消されので、6つの left-leaning 赤黒木の全ての条件がみたされるようになる。