赤黒木をやってみよう

赤黒木のルールは

1. ルートは常に黒
2. 新ノードは赤で右に追加
3. 右下の子だけが赤の時左回り
4. 両方の子が赤の時上下の色を変える

まずはルートに２を挿入

右下が赤なので左回り。

ルートは黒に

次のノードを挿入

両方の子が赤なので色を交換

ルートは黒に

ノードを追加

右下が赤なので左回り。

ノード追加

両方の子が赤なので色を交換

４が右下の赤になるので左回り

ノード追加

右下の赤は左回り

ノード追加

両方の子が赤なら色をひっくり返す。

もう一回

ひっくり返す。

ルートは黒