【データ構造】赤黒木（Red-Black Tree）への挿入手順をわかりやすく解説

赤黒木（Red-Black Tree）とは、木を構成する各ノードが「赤」または「黒」のいずれかの色で塗り分けられた自己平衡型二分探索木です。赤黒木に対して実行できる基本操作には、検索・挿入・削除の3種類があります。

ここでは、次のような赤黒木に新しい要素を挿入するケースを想定して、具体的な手順を解説していきます。

赤黒木の平衡条件

赤黒木への挿入の基本的な考え方はとてもシンプルです。通常の二分探索木と同じように、根ノードから順に値を比較しながら適切な位置へ挿入していきます。ただし、赤黒木では挿入後に木のバランスを保つための追加処理が必要になる点が特徴です。

そのために、まず赤黒木が「平衡している」とみなされるための条件を理解しておきましょう。以下の4つの条件がすべて満たされているとき、赤黒木は平衡状態にあるといえます。

• 根ノードは必ず黒である

• すべてのノードは赤または黒のいずれかである

• 赤いノードの子は必ず黒である（赤と赤が連続してはならない）

• 根から葉までのすべての経路に含まれる黒いノードの数は等しい

新しいノードを追加するたびに、これらの条件を崩さないよう修正を加えていくのが、赤黒木における挿入処理の本質です。

赤黒木への挿入手順

赤黒木に新しい要素を挿入する際は、以下のステップに従います。

• 木が空かどうかを確認する。木が空の場合は、新しいノードを挿入して色を黒に設定します（根ノードは常に黒でなければならないためです）。

• 木が空でない場合は、新しいノードを葉ノードとして末端に追加し、色を赤に設定します。

• 新ノードの親が赤で、親の兄弟（叔父ノード）も赤の場合は、親と叔父の色を反転させ、さらに祖父ノードの色も反転させます（祖父が根ノードでない場合）。祖父が根ノードである場合は、親と叔父の色のみを反転させます。

• 新ノードの親が赤で、叔父ノードが空（NULL）の場合は、新ノードと親に対して回転操作（左左回転または左右回転）を実行します。

回転操作には「左左回転（Left-Left Rotation）」と「左右回転（Left-Right Rotation）」の2種類があり、それぞれ特定の条件下でのみ適用されます。適用条件は次の通りです。

• 新ノードの親が赤で、叔父ノードが空（NULL）である場合に、左回転または右回転を行う。

• 左左回転では、親と祖父の色を反転させたうえで、親を祖父の位置へ、祖父を子の位置へと入れ替える。

アルゴリズム（擬似コード）

ここまで説明した一連の挿入処理を、擬似コードで表現すると次のようになります。

RBTreeInsertion(root, key)

// 挿入する新しいノードの色は赤に設定
color[key] ← Red
while(key≠root and color(p[key])=Red)
do if p[key]=left(p[p[key]])
   Then y←right[p[p[key]]]
// 新ノードの親が赤の場合（祖父が根ノードでないとき）は色を反転させる
   if color[y]←Red
   then color(p[key])←Black
      color(p[p[key]])←Red
      key←p[p[key]]
   else if key←right[p[key]]
      then key←p[key]
   // 新ノードの親が赤で、その兄弟（叔父ノード）がNULLの場合
   LeftRotate(root,key)
   color(p[key])←Black
   color(p[p[key]])←Red
RotateRight(root,p[p[key]])
else 左右の部分木を入れ替えてバランスを取る
color(root)←Black