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

ノードの追加は、二分探索木と同じように根からノードとたどっていずれかの葉へ追加するけれど、この時、必ず赤色で追加する。
※ 赤で追加すれば赤黒木の条件5.の木の高さを満たしたまま追加できるから。

まず、木が空のときについて考える。
木が空の場合に追加される場所は根。
上記のとおり赤ノードで追加すると木は次の図になる。
※ 図の中の■は葉

この状態は、赤黒木の条件 2 だけを満たしていない。
つまり、追加した赤ノードを黒に変えるだけで赤黒木の全ての
条件を満たすことができる。
実際に、色を変えると木は次の図になる。

赤ノードが木の中にないので、いうまでもないけれど
left-leaning 赤黒木の追加条件 6 も満たしている。
※ 全ての赤ノードは、黒ノードの左側の子ノードである