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

末端ノード◎^a を取り除くとき、その位置と色で 3つの場合に分けてみる。

1. 赤ノードのとき
2. 赤ノードの子を持つ黒ノードのとき
3. 赤ノードの子を持たない黒ノードのとき

1.の取り除くノード ○^a の色が赤のときを考えてみる。
赤ノードなので ○^a は黒ノードの左のはず。このとき取り除いた後も 6つの left-leaning 赤黒木の条件を全て満たしていることがわかる。

2.の取り除くノード ●^a が赤色の子ノード ○^z を持つときを考えてみる。

●^a が取り除かれたことで ○^z の葉と根までの黒ノード数が一つ減って ○^z-1 と変わって、木の枝が切れてしまっている状態となる。

まず ○^z-1 を ●^a のあった位置に移す。
次に ○^z-1 の色を黒に変ると ○^z-1 の葉から根までの間の黒ノードの数が一つ増えて ●^z となり 6つの left-leaning 赤黒木の条件を満たすようになることがわかる。

最後に 3.の赤ノードの子を持たない黒ノードを取り除くときについて 4つの場合に分けてみた。

1. 赤ノードの右の黒ノードを取り除くとき
2. 赤ノードの左の黒ノードを取り除くとき
3. 黒ノードの右の黒ノードを取り除くとき
4. 黒ノードの左の黒ノードを取り除くとき

次回から、この 4つの場合を一つずつ考えてみる。