追加するノード○
aが、ある末端の赤ノード○
zより小さいとき、または等しいとき(○
a≦○
z)を考えてみる。
○
z は赤ノードのなので、黒の親ノード ●
y の左ノードのはずで、この時、実際にノード○
a を追加するときの木は次の図のようになる。
この木の状態は、赤ノード ○
z の左が赤ノード ○
a になって、
赤黒木の条件 4. を満たさなくなっている。
※ 4. 赤のノードの子ノードはすべて黒である。
このときの ○
z と ○
a の関係をここでは、(赤)左(赤)状態とよぶことにする。
崩れてしまった条件 4. を木の回転で平衡を取り戻してみる。
回転によって○
z の右ノードの根から葉までの黒ノードの数は変わらないけれど、○
z の左ノードの根から葉までの黒ノードの数は一つ減っているので、○
a-1 で表す。
このとき ○
a の色を黒に変えれば左側のノードは、根から葉までの黒ノードの数を一つ増やせることがわかる。実際に変えてみると図は次のようになる。
無事に追加できたけれど、ここで木の回転の前の ●
y の他のノードとの関係を考えてみる。
●
y は黒ノードだったので、回転の前の ●
y は次の 5つ場合があり得る。
- ●y は根だった場合。
- 黒ノード ●x の左ノードだった場合。
- 黒ノード ●x の右ノードだった場合。
- 赤ノード ○x の左ノードだった場合。
- 赤ノード ○x の右ノードだった場合。
つまり、回転の後の木の状態は次の図のどれかのはず。
この 5つのどの図にあるか調べることが必要なとき、ここでは赤ノード ○
z を(赤)頭状態と呼ぶことにする。
図の中の 1. 〜 4. の木の状態は、ここまでの説明で出てきた形になっていることがわかる。
- ノードの追加(根)
- ノードの追加(黒ノードの左) … (黒)左(赤)状態
- ノードの追加(黒ノードの右) … (黒)右(赤)状態
- ノードの追加(赤ノードの左) … (赤)左(赤)状態
赤黒木の条件または、left-leaning 赤黒木の追加条件を満たしていない 1. と 3. と 4. は同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。
同じように 5. の図は、次で説明するノードの追加(赤ノードの右)と同じ形になって同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。
(赤)頭状態は、一段づつ根に近づきながら、最終的に (黒)左(赤) 状態になって、left-leaning 赤黒木の 6つの全ての条件を満たして操作が終わるか、根まで登って操作が終わる。