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

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