前回の記事で、赤黒木の導入について説明しました。 今回の投稿では、挿入について説明します。 AVLツリーの挿入では、挿入後のバランス調整を行うためのツールとして回転を使用しました。 Red-Blackツリーでは、2つのツールを使ってバランシングを行います。
- Recoloring
- Rotation
Recolouringはノードの色の変更である、すなわち、それが赤であれば黒に変更し、逆も同様である。 NULLノードの色は常に黒であることに注意しなければならない。 さらに、まず再カラーリングを行い、それでもダメなら回転を行う。 以下はその詳細なアルゴリズムである。 このアルゴリズムには、おじさんの色によって主に二つのケースがある。 おじさんの色が赤の場合、再カラーリングを行う。 おじさんが黒い場合は、回転と再カラーを行います。
私たちが扱う表現は次のとおりです。
この表現は X
Logic:
最初に、二分木と同じようにノードを挿入して赤い色を割り当てなければならない。 そのノードがルートノードであれば、その色を黒に変更しますが、そうでない場合は、親ノードの色をチェックします。 親ノードの色が黒であれば、その色は変更しませんが、そうでない場合、つまり赤である場合は、そのノードの叔父の色をチェックします。 ノードの叔父の色が赤であれば、ノードの親と叔父の色を黒に、祖父の色を赤に変更して、彼（つまり祖父）に対して同じプロセスを繰り返します。
ただし、ノードの叔父の色が黒の場合、4つのケースが考えられます。
- LL 左回転の場合:
- LR 右回転の場合: LR 左回転の場合は、左側のノードの色が黒になります。
- Right Right Case (RR rotation):
- Right Left Case (RL rotation):
ここで、これらの回転後、ノードの色が一致しなければ再カラーリングすることです。
アルゴリズム:
xを新しく挿入されたノードとする。
- 標準のBST挿入を行い、新しく挿入されたノードの色を赤にする。
- xがルートの場合、xの色を黒にする（完全木の黒い高さは1増加）。
- xの親の色が黒ではなく、xはルートではないときは以下を実行します。
a) xの叔父がREDの場合（性質4から祖父母は黒でなければならない）
(i) 親と叔父の色をBLACKに変更する。
(ii)祖父母の色をREDとする。
(iii) x = xの祖父母に変更し、新しいxについて手順2と3を繰り返す。b) xの叔父がBLACKの場合、xの構成は4つ考えられる。 xの親(p)とxの祖父母(g) (これはAVL木に似ている)
(i) 左左ケース (pがgの左子、xがpの左子)
(ii) 左右ケース (pがgの左子、xがgの左子)
(iii) 右左ケース (pがgの左子、xがgの左子) gの左子、xはpの右子）
(iii) 右右ケース（ケースiのミラー）
(iv) 右左ケース（ケースiiのミラー）
例． 空の木に要素3、21、32、17を持つ赤黒い木を作成する
解決策。
最初の要素が挿入されるとき、ルートノードとして挿入され、ルートノードは黒い色を持っているので、黒い色を獲得する。
新しい要素は常に赤い色で挿入されて、21 > 3 としてルートノードの右サブツリーに含まれるようになる。
さて、32を挿入すると、赤の親子ペアがあり、赤黒木規則に違反するので、回転させる必要があることがわかります。 さらに、RR回転の条件（ルートノードのNULLノードを黒とみなす）を見ると、回転後はルートノードが赤になれないので、木の再カラーリングを行い、上記のような木になる。
ここで、新しい要素を挿入すると、赤色の親ノードと子ノードが再び表示されるので、ここで再カラーリングする必要があります。 親ノードと叔父ノードの両方が赤い色を持っていることがわかりますので、それらの色を単に黒に変更し、祖父の色を赤に変更します。 さて、祖父はルートノードなので、再びその色を黒に変更すると、上のようなツリーになります。
最終的なツリー構造。
最終的なツリーは次のようになります。
上記のアルゴリズムの完全な実装は、赤黒木挿入のCプログラムを参照してください。
赤黒木｜セット3（削除）