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つの全ての条件を満たして操作が終わるか、根まで登って操作が終わる。