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

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

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

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

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

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

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 赤黒木の全ての条件がみたされるようになる。

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つの場合を一つずつ考えてみる。

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

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

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

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

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

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

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

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

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

最後に追加するノード○^aが、ある末端の赤ノード○^zより大きいとき(○^z<○^a)を考えてみる。

○^z は赤ノードのなので、黒の親ノード ●^y の左ノードのはずで、この時、実際にノード○^a を追加するときの木は次の図のようになる。

この木の状態は、赤ノード ○^z の右が赤ノード ○^a になって、
赤黒木の条件 4. を満たさなくなっている。
※ 4. 赤のノードの子ノードはすべて黒である。

さらに、left-leaning 赤黒木の追加条件 6. も崩れている。
※ 6. 全ての赤ノードは、黒ノードの左側の子ノードである。

この赤ノード ○^z の状態を (赤)右(赤) 状態と呼ぶことにする。

崩れてしまった 2つの条件を木の回転で取り戻してみる。

この木の状態は、前回の説明のノードの追加(赤ノードの左)と同じ形で、赤ノード ○^a は (赤)左(赤) 状態になった。

さらに、(赤)左(赤) のときに赤黒木の条件 4. 満たすための操作をすると (赤)頭状態になる。

(赤)頭状態のときに気にしなければならないことは前回の説明で終えているので、left-leaning 赤黒木のノードの追加するときについての全ては説明が済んだことになる。

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

追加するノード○^aが、ある末端の赤ノード○^zより小さいとき、または等しいとき(○^a≦○^z)を考えてみる。

○^z は赤ノードのなので、黒の親ノード ●^y の左ノードのはずで、この時、実際にノード○^a を追加するときの木は次の図のようになる。

この木の状態は、赤ノード ○^z の左が赤ノード ○^a になって、
赤黒木の条件 4. を満たさなくなっている。
※ 4. 赤のノードの子ノードはすべて黒である。
このときの ○^z と ○^a の関係をここでは、(赤)左(赤)状態とよぶことにする。

崩れてしまった条件 4. を木の回転で平衡を取り戻してみる。

回転によって○^z の右ノードの根から葉までの黒ノードの数は変わらないけれど、○^z の左ノードの根から葉までの黒ノードの数は一つ減っているので、○^a-1 で表す。

このとき ○^a の色を黒に変えれば左側のノードは、根から葉までの黒ノードの数を一つ増やせることがわかる。実際に変えてみると図は次のようになる。

無事に追加できたけれど、ここで木の回転の前の ●^y の他のノードとの関係を考えてみる。
●^y は黒ノードだったので、回転の前の ●^y は次の 5つ場合があり得る。

1. ●^y は根だった場合。
2. 黒ノード ●^x の左ノードだった場合。
3. 黒ノード ●^x の右ノードだった場合。
4. 赤ノード ○^x の左ノードだった場合。
5. 赤ノード ○^x の右ノードだった場合。

つまり、回転の後の木の状態は次の図のどれかのはず。
この 5つのどの図にあるか調べることが必要なとき、ここでは赤ノード ○^z を(赤)頭状態と呼ぶことにする。

図の中の 1. 〜 4. の木の状態は、ここまでの説明で出てきた形になっていることがわかる。

1. ノードの追加(根)
2. ノードの追加(黒ノードの左) … (黒)左(赤)状態
   
3. ノードの追加(黒ノードの右) … (黒)右(赤)状態
4. ノードの追加(赤ノードの左) … (赤)左(赤)状態

赤黒木の条件または、left-leaning 赤黒木の追加条件を満たしていない 1. と 3. と 4. は同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。

同じように 5. の図は、次で説明するノードの追加(赤ノードの右)と同じ形になって同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。

(赤)頭状態は、一段づつ根に近づきながら、最終的に (黒)左(赤) 状態になって、left-leaning 赤黒木の 6つの全ての条件を満たして操作が終わるか、根まで登って操作が終わる。

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

追加するノード○^aが、ある末端の黒ノード●^zより大きいとき(●^z<○^a)を考えてみる。

実際に追加すると木は次の図になる。

新しく赤ノード○^aが追加された木は、赤黒木の 5つの条件を満たしているけれど、left-leaning の追加条件を満たしていない。
※ 6. 全ての赤ノードは、黒ノードの左側の子ノードである。

この●^zと○^aの関係をここでは、(黒)右(赤) 状態と呼ぶことにする。

ここで、条件 6. を満たすようにするために、木の回転を行って平衡を取り戻してみる。

回転後は、○^aの左右で平衡が崩れて、○^aの右側の葉は根までの黒ノードの数が一つ少なくなってしまっている。この状態を■^-1で表すことにする。

この状態は ○^aを黒にして ●^zを赤に色を変えれば ●^aの左側のノードは、根から葉までの黒ノードの数を変えずに、●^aの右側のノードの根から葉までの黒ノードの数を一つ増やせることがわかる。実際に変えてみると図は次のようになる。

黒ノード●^a の左に赤ノード○^z がぶら下がる形になったので、○^z は left-leaning 赤黒木の追加条件 6. を満たしている。

また ●^a は黒ノードなので、●^a がある黒ノードの左右どちらかの子ノードであっても、ある赤ノードの左右どちらかの子ノードであっても、left-leaning 赤黒木の追加条件 6. を崩すことなないし、赤黒木の条件 2. を満たしている。
※ 2. 根は黒である。

さらに、崩れていた赤黒木の条件 5. が色の入れ替えで木の根から葉までの黒ノードの数が同じになって条件を満たすようになった。
※ どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である。

無事にノードの追加ができた。