以下の続きです。
ノードの挿入
Red Black Tree でノードの挿入は、以下の3つのステップで行われます。
普通の2分探索木の挿入を行う
まずは、普通の2分探索木と同じように、ノードを挿入します。
挿入するノードの色を赤にする
挿入したノードの色を赤にします。
Red Black Tree の条件チェックを行い、修正する
新しいノードの挿入後、Red Black Treeの条件が守られているか確認をします。
- 各ノードは赤か黒の色をもつ。
- 根は黒である。
- 葉 (NIL) はすべて黒である。
- 赤のノードは黒ノードを 2つ子に持つ。（したがって、赤のノードの親ノードは黒である）。
- 任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である。
Red Black Tree をRBT、挿入するノードをN (New Node)、親をP (Parent Node)、叔父をＵ (Uncle Node)、兄弟をＳ (Sibling Node)、親の親をＧ (Grandparent Node) として、具体的に場合分けを行います。
それぞれのノードは、図にすると以下のような関係になっています。
RBT が空の場合
何もない木にＮを挿入する時は、Ｎは根になり、ルール2によりＮの色が黒になります。
Ｐが黒の場合
新しいノードＮの親Ｐが黒の場合は、ルール違反がないので、特に木を操作が必要ありません。
Ｐが赤の場合
ルール４に違反しているので、木の修正が必要になります。
新しいノードＮと親のＰは赤です。Ｇはルールにより黒です。
この場合、叔父にあたるＵの色により場合分けが起こります。
Ｐが赤でＵも赤の場合
この場合はＰとＵとＧの色を反転させます。
ここから分かりやすいように、それぞれのノードに数字を加えています。
ＵとＰの赤を黒に、Ｇの黒を赤にします。
Ｐが赤でＵは黒（またはNull）の場合
この場合は回転の操作が必要になります。
ＰがＧの左側の子か右川の子か、ＮがＰの左側の子か右側の子かで、必要な回転の操作が異なるので、さらに場合分けを行います。
ＵがNullの場合は、葉はNILで全て黒であるというルールに基づき、Ｕは黒であると判断します。
Ｐが赤でＵは黒、ＰはＧの右側の子でＮはＰの右側の子である場合
左回転を行います。
ＰとＧの色を反転します。
Ｐが赤でＵは黒、ＰはＧの右側の子でＮはＰの左側の子である場合
右回転を行います。
左回転を行います。（ここからの操作は、上の左回転、色反転と同じ操作になります。）
ＮとＧの色を反転します。
Ｐが赤でＵは黒、ＰはＧの左側の子でＮはＰの左側の子である場合
この場合は、「Ｐが赤でＵは黒、ＰはＧの右側の子でＮはＰの右側の子である場合」と左右対称の操作を行います。
右回転を行います。
ＰとＧの色を反転します。
Ｐが赤でＵは黒、ＰはＧの右側の子でＮはＰの左側の子である場合
この場合は、「Ｐが赤でＵは黒、ＰはＧの左側の子でＮはＰの右側の子である場合」と左右対称の操作を行います。
左回転を行います。
右回転を行います。
ＮとＧの色を反転します。
疑似コード
Red Black Tree の挿入を疑似コードにまとめます。
RedBlackTree-INSERT(T, n)
// まずは通常の2分探索の挿入を行う。
BinarySearchTree-INSERT(T, n)
// 親が赤の場合は木の修正が必要
while n.parent.color == RED
// 親が爺の右側の子である場合
if n.parent == n.parent.parent.right
// 叔父は爺の左側の子
u = n.parent.parent.left
// 叔父が赤であれば、親、爺、叔父の色を反転させる
if u.color == RED
u.color = BLACK
n.parent.color = BLACK
n.parent.parent.color = RED
// 爺の色が変わったので、再び確認
n = n.parent.parent
// 叔父の色が黒の場合は、回転の操作を行う。
else
// 新しいノードが親の左側の子である場合は、親を軸に右回転
if n == n.parent.left
n = n.parent
RIGHT-ROTATE(T, n)
// 色の反転
n.parent.color = BLACK
n.parent.parent.color = RED
// 左回転
LEFT-ROTATE(T, n.parent.parent)
// 親が爺の左側の子である場合 上の“left” と “right”を入れ替える
else
// 叔父は爺の右側の子
u = n.parent.parent.right
// 叔父が赤であれば、親、爺、叔父の色を反転させる
if u.color == RED
u.color = BLACK
n.parent.color = BLACK
n.parent.parent.color = RED
n = n.parent.parent
// 叔父の色が黒の場合は、回転の操作を行う。
else
// 新しいノードが親の右の子である場合は、親を軸に左回転
if n == n.parent.right
n = n.parent
LEFT-ROTATE(T, n)
// 色の反転
n.parent.color = BLACK
n.parent.parent.color = RED
// 右回転
RIGHT-ROTATE(T, n.parent.parent)
// 根の色は黒。
T.root.color = BLACK