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 赤黒木のノードの追加するときについての全ては説明が済んだことになる。