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

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

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

「ノードの削除(赤ノードの右の黒)」と同様に ●^y の色を赤に変えると ○^z-1 となって、○^z-1 と ○^y の関係は (赤)右(赤) 状態となる。

「ノードの追加(赤ノードの右)」と同じように操作すると、

○^y-1 は (赤)頭^-1 状態になるので、色を黒に変えて平衡をとりもどす。