空間
O
(
n
)
{\displaystyle {\mathcal {O}}(n)}
図1: 明示的な葉(NIL)を持つ赤黒木
図2: 左右の暗黙のドッキングポイントを持つ赤黒木
赤黒木は二分木 の一種であり、コンピュータ科学 においてテキストの断片や数（例:図1や図2の数値）などの比較 可能なデータ を組織化する際に用いられる。データは二分木のノード に配置され、そのうちでスタート地点となる「どのノードの子 でもないノード」を根 という。根は2つまでの「子」（根に接続しているノード）をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も……、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。
赤黒木における葉 （図1の NIL ）はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなくヌルポインタ で表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。
赤黒木は二分探索木 であり、すなわち、各ノードのもつ値が
そのノードの右部分木に含まれるノードのもつ値より大きくない
そのノードの左部分木に含まれるノードのもつ値より小さくない という性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。
ノードの黒深さ は、根からそのノードまでの黒ノードの数（すなわち黒祖先の数）と定義される。赤黒木の黒高さ は、根から葉までのどの経路にもある黒のノードの数であり、要件5 により一定である（代わりに、任意の葉のノードの黒深さとして定義することもできる）。 [3] :154–165
ノードの黒高さは、そのノードが根とする部分木の黒高さである。この記事では、NILノードの黒高さは0とする。なぜなら、その部分木は図2が示唆するように空であり、その木の高さも0であるからである。
用途と利点 赤黒木というデータ構造 は、最悪のケースにおける計算量 が、データの挿入・削除・検索のいずれにおいても、データ構造のうちで最善のものの一つである。このため、リアルタイム・コンピューティング のような時間計算量に敏感なアプリケーションにおいて有益である。また、計算幾何学 で用いるデータ構造など、最悪のケースでの計算量を保証する必要のあるデータ構造の基礎としても有用なことが多い。
赤黒木と同様に平衡二分木であるAVL木 は、赤黒木に比べて平衡性についての条件が厳しく、そのためAVL木では最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。
赤黒木は関数型プログラミング においても部分的に重要であり、永続的データ構造 を実現するデータ構造の一つとして、変更後も以前の値を保持し続けるような連想配列 や集合 を実装する際に広く用いられるものの一つである。なお、このような永続性 をもったタイプの赤黒木では、挿入や削除のたびに、時間だけでなく
O
(
log
n
)
{\displaystyle {\mathcal {O}}(\log n)}
Animation of tree rotations taking place.
RBnode * RotateDirRoot (
RBtree * T , // 赤黒木
RBnode * P , // 部分木の根 ( Tの根であってもよい )
int dir ) { // dir ∈ { LEFT, RIGHT }
RBnode * G = P -> parent ;
RBnode * S = P -> child [ 1 - dir ];
RBnode * C ;
assert ( S != NIL ); // 真のノードへのポインターを要求する
C = S -> child [ dir ];
P -> child [ 1 - dir ] = C ; if ( C != NIL ) C -> parent = P ;
S -> child [ dir ] = P ; P -> parent = S ;
S -> parent = G ;
if ( G != NULL )
G -> child [ P == G -> right ? RIGHT : LEFT ] = S ;
else
T -> root = S ;
return S ; // 部分木の新しい根
}
#define RotateDir(N,dir) RotateDirRoot(T,N,dir)
#define RotateLeft(N) RotateDirRoot(T,N,LEFT)
#define RotateRight(N) RotateDirRoot(T,N,RIGHT)
サンプルコードと挿入図・削除図に関する注記
この提案では、挿入と削除（非常に単純なケースを除く）の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復（リバランシング）するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。
変数 N はカレントノードを表し、図中では N と表される。
図には3つの列と2～4つのアクションが含まれる。
左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。[6] 動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件 に違反している。N は青い枠で囲まれ、他のノードはN との関係によってラベル付けされている。
回転 が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。[7]
まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードN で挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、N に対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。
番号が書かれた黒丸を頂点とする三角形（要件4 に従ってその親に接続）を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。
コメント
簡単のため、サンプルコードでは論理和 と
U == NIL || U->color == BLACK // 黒とみなす
論理積 を
U != NIL && U->color == RED // 黒でないとみなす 使用する。
そのため、U == NIL の場合、論理和・論理積ともに式全体が評価されないことに留意する必要がある。この場合、どちらの場合も U->colorは評価されない（短絡評価 参照）。黒とみなすというコメントは、要件2 に準じたものである。）
この提案[6] if文の発生頻度を大幅に減らすことができる。 挿入 挿入は、新しい（非NIL）ノード（N とする）を、二分探索木における、間順走査 での先行ノードのキーが新しく挿入するノードのキーより小さく、かつ新しく追加するノードのキーが後行ノードのキーより小さくなるNILノードの位置に配置することから始まる。（多くの場合、この位置は、挿入操作の直前に木内を探索した結果であり、ノード P と、P->child[dir] == NIL を持つ方向 dir で構成される。）新しく挿入されたノードは一時的に赤色となり、すべての経路に以前と同じ数の黒ノードが含まれるようにする。しかし、その親ノード（例えばP ）が赤である場合、この操作は赤違反 を引き起こす。
void RBinsert1 (
RBtree * T , // -> 赤黒木
struct RBnode * N , // -> 挿入するノード
struct RBnode * P , // -> Nの親ノード（NULLでも可）
byte dir ) // Nを挿入するPの側（LEFTまたはRIGHT）
{
struct RBnode * G ; // -> Pの親ノード
struct RBnode * U ; // -> Nのおじ
N -> color = RED ;
N -> left = NIL ;
N -> right = NIL ;
N -> parent = P ;
if ( P == NULL ) { // 親がない場合
T -> root = N ; // Nが赤黒木Tの新しい根とし、
return ; // 挿入完了。
}
P -> child [ dir ] = N ; // NをPのdir側の子として挿入する
// (do while)ループを開始する
do {
不変条件 を持つ。
カレントノードN は、各反復の開始時に
要件4 は、P も赤の場合（N で赤違反 ）、N ←P を除き、すべてのペア node←parent で満たされる。他のすべての性質（要件5 を含む）は、木全体で満たされている。 挿入図に関する注記
前の状態 ケース
回転 割り当て 後の状態 →次
Δh
P G U x P G U x
—
I3 →
I1 →
—
I4 →
I2 N :=G ?
?
2
i
I5 P ↶N N :=P o
I6 0
o
I6 P ↷G →
挿入: この一覧表では、前の列で、ノード群の起こりうるすべてのケース[8]
図表において、P はN の親、G はN の祖父母、U はN のおじを表す。
図では、P はG の左の子として表されているが、P は左右どちら側にも存在する可能性がある。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。
N は挿入ノードであるが、操作を進めると他のノードもカレントノードになる可能性がある（ケースI2 図で、P がN と同じく赤色の場合は、赤違反 であることを表している。
x列は子の向きの変化を表し、o（外側）はP とN がともに左またはともに右の子であることを意味し、i（内側）はP からN への方向がG からP への方向と違うことを意味する。
前の状態 の列グループはケースを定義し、その名前がケース の列で与えられる。そのため、空欄のセルの値は無視される。したがって、ケースI2 N の子方向は1つだが、サンプルコードでは両方の可能性をカバーしている。一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
回転 の列は、回転がリバランシングに寄与しているかどうかを示す。割り当て の列は、後続のステップに入る前にN への割り当てが行われることを示す。これにより、他のノードP 、G 、U も同様に再割り当てが行われる可能性がある。ケースによってノードに変更があった場合、後の状態 の列グループに示される。
次 の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態 の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。ループは挿入ケース1 と挿入ケース2 の章に含まれ、ケースI2 G が新しいカレントノードN になるという意味で、リバランシングの問題が
Δ
h
=
2
{\displaystyle \Delta h=2}
最初の反復
挿入ケース2 親P とおじU の両方が赤なら、両方を黒に塗り替え、祖父母G を赤にすることで要件5 を維持することが可能となる。親やおじを通る経路は必ず祖父母を通るので、これらの経路上の黒ノードの数は変わっていない。しかし、祖父母G が赤の親を持つ場合、要件4 に違反する可能性がある。G をN にラベル付けした後、ループ不変条件が満たされるので、1つ上の黒レベル（＝2の木レベル）でリバランシングを繰り返すことができるようになる。
// Case_I2 (PとUが赤):
P -> color = BLACK ;
U -> color = BLACK ;
G -> color = RED ;
N = G ; // 新しいカレントノード
// 1段階上の黒を反復
// (= 2の木レベル)
} while (( P = N -> parent ) != NULL );
// (do while)ループの終了
挿入ケース3 挿入ケース2 は
h
−
1
2
{\displaystyle {\tfrac {h-1}{2}}}
最初の反復
挿入ケース5 親P は赤だが、おじU は黒。最終的な目標は、親ノードP を祖父母の位置に回転させることだが、N がG の内側の孫の場合（つまり、N がG の右子の左子またはG の左子の右子の場合）、これはうまくいかない。P でdir-回転N とその親P の役割が入れ替わる。この回転により、N を通る経路（図中の2の部分木）が追加され、P を通る経路（図中の4の部分木）が削除される。しかし、P もN も赤なので、要件5 は維持される。要件4 はケース6で復元される。
Case_I56 : // Pは赤 && Uは黒:
if ( N == P -> child [ 1 - dir ])
{ // Case_I5 (Pは赤 && Uは黒 && NはGの内側の孫):
RotateDir ( P , dir ); // Pは根にはならない
N = P ; // 新しいカレントノード
P = G -> child [ dir ]; // Nの新しい親
// Case_I6に該当する
}
挿入ケース6 カレントノードN は、G の外側の孫（左子の左子または右子の右子）であることが確定している。今度はG で(1-dir)-回転G の代わりにP を置き、P をN とG の親とすると、要件4 に違反するため、G は黒、G の前の子P は赤となる。P とG の色を入れ替えた後の木は、要件4 を満たしている。黒G を経由していた経路はすべて黒P を経由するようになったので、要件5 も満たしたままである。
// Case_I6 (Pは赤 && Uは黒 && NはGの外側の孫):
RotateDirRoot ( T , G , 1 - dir ); // Gは根である可能性がある
P -> color = BLACK ;
G -> color = RED ;
return ; // 挿入完了
} // RBinsert1の終了
このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレース である。
削除（シンプルなケース） ラベルN は、入力時に削除されるノードであるカレントノードを表す。
もし、N が根で、非NILの子を持たない場合、N はNILノードに置き換えられ、その後、木は空になり、赤黒木の形になる。
もし、N が2つの非NILの子を持つ場合、N の左側の部分木の最大要素（これは間順走査でのN の先行ノード）またはN の右側の部分木の最小要素（これは間順走査でのN の後行ノード）のいずれかへの追加のナビゲーションは、（ここ に示すように）N との間に他のノードが存在しないノードを見つける。この置換ノードはR と呼ばれ、部分木の最大または最小要素として、最大で1つの非NILの子を持つ。ユーザが定義したノード構造からソフトウェアを完全に独立させるために、N との間のすべての赤黒い木のポインタは、R との間のすべての赤黒木のポインタと交換され、N のRB-colorもR に与えられる。ノード間の順序関係は、N とR 間の順序（N を除去することによって直ちに解決する問題）を除いて保存され、N は最大1つの非NILの子を持つ。
もし、N がちょうど1つだけ非NILの子を持つなら、N の子は赤でなければならない。もしN の子が黒なら、要件5 によって2つ目の黒の非NILの子が強制されるからである。
もし、N が赤のノードである場合、非NILの子を持つことはできない。なぜなら要件4 によりN の子は黒でなければならないからであり、さらに、先ほどの議論と同様に、黒い子を1つだけ持つことはできない。その結果、赤のノードN は子を持たず、単に削除されるだけである。
もし、N が黒ノードであれば、1つの赤の子ノードを持つか、非NILの子ノードを全く持たない場合がある。N が赤の子ノードを持っている場合は、赤の子ノードを黒く塗った後、その子ノードとN を置き換えるだけである。
非根の黒葉ノードの削除 複雑なケースは、N が根でなく、黒色で、NILの子だけを持つ（⇔色が正確な子を持たない）場合である。最初の反復で、N はNILに置き換えられる。
void RBdelete2 (
RBtree * T , // -> 赤黒木
struct RBnode * N ) // -> 削除対象ノード
{
struct RBnode * P = N -> parent ; // -> Nの親ノード
byte dir ; // Nの位置するPの側 (∈ { LEFT, RIGHT })
struct RBnode * S ; // -> Nの兄弟ノード
struct RBnode * C ; // -> 近いおい
struct RBnode * D ; // -> 遠いおい
// P != NULL, Nは根ではないので。
dir = childDir ( N ); // ノードNが位置する親Pの側（LEFT か RIGHT）
// 親PのNをNILに置き換える:
P -> child [ dir ] = NIL ;
goto Start_D ; // ループに移動する
// (do while)-ループの開始:
do {
dir = childDir ( N ); // ノードNの位置する親Pの側
Start_D :
S = P -> child [ 1 - dir ]; // Nの兄弟 (黒高さ >= 1)
D = S -> child [ 1 - dir ]; // 遠いおい
C = S -> child [ dir ]; // 近いおい
if ( S -> color == RED )
goto Case_D3 ; // Sが赤 ===> P+C+Dが黒
// S is black:
if ( D != NIL && D -> color == RED ) // 黒でないとみなす
goto Case_D6 ; // Dが赤 && Sが黒
if ( C != NIL && C -> color == RED ) // 黒でないとみなす
goto Case_D5 ; // Cが赤 && S+Dが黒
// ここでは、両方のおい == NIL (最初の反復) または黒 (上位の反復).
if ( P -> color == RED )
goto Case_D4 ; // Pが赤 && C+S+Dが黒
不変条件 を持つ。
各反復の始めに、N の黒高さは反復番号から1を引いたものに等しく、これは最初の反復では0であり、上位の反復ではN は真の黒ノード
N を通る経路の黒ノード数は削除前より1つ少ないが、それ以外の経路では変化しないので、他の経路が存在する場合はP で黒違反 が発生することになる。他のすべての性質（性質4 を含む）は、木全体で満たされている。 削除図に関する注記
前の状態 ケース 回転 割り当て 後の状態 →次
Δh
P C S D P C S D
—
D2 →
D3 P ↶S N :=N ?
?
?
0
D1 N :=P ?
?
1
D4 →
D5 C ↷S N :=N D6 0
D6 P ↶S →
削除: この一覧表では、前の状態 の列で、ノード群の起こりうるすべてのケース[8]
図表において、P がN の親ノード、S がN の兄弟ノード、C がS のN と同じ方向の子ノード（近いおい）、D がS のもう一方の子ノード（遠いおい）となる（S は削除前のN の黒高さが1でなければならないので最初の反復でNILノードにはなれないが、C とD はNILノードになってもよい）。
図では、カレントノードN が親P の左の子となっているが、N は左右どちら側にも存在することが可能である。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。
削除の初め（最初の反復）では、N は削除されるノードの代わりにNILノードである。親ノードでの位置だけが重要なので、削除図の左欄には N はNILノードで左の子）で記号化される。操作を進めると、（黒高さ ≥ 1の）非NILのノードもカレントノードになる可能性がある(例：ケースD1
削除図にある黒丸（N を通る経路は他の経路より黒丸が1つ少ないことがわかる。これはP での黒違反 を意味する。
前の状態 の列グループはケースを定義し、その名前がケース の列で与えられる。そのため、空欄のセルの値は無視される。一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
回転 の列は、回転がリバランシングに寄与しているかどうかを示す。割り当て の列は、後続のステップに入る前にN への割り当てが行われることを示す。これにより、他のノードP 、C 、S 、D も同様に再割り当てが行われる可能性がある。ケースによってノードに変更があった場合、後の状態 の列グループに示される。
次 の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態 の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。ループは Start_D から削除ケース1 までのセクションに含まれ、親P が新しいカレントノードN になることで、リバランスの問題が木で
Δ
h
=
1
{\displaystyle \Delta h=1}
最初の反復
削除ケース1 P 、S 、S の子は黒である。S を赤にした後、S を通るすべての経路（正確にはN を通らない経路）は、黒ノードが1つ少なくなる。ここで、P をルートとする部分木のすべての経路は同じ数の黒ノードを持つが、P を通らない経路より1つ少ないので、まだ要件4 に違反している可能性がある。P をN にラベル付けした後、ループ不変条件 が満たされるので、1上の黒レベル（=1上の木レベル）でリバランシングを繰り返すことができる。
// Case_D1 (P+C+S+Dは黒):
S -> color = RED ;
N = P ; // 新しいカレントノード (根かもしれない)
// 1黒レベル(1木レベル)を上げながら反復する
} while (( P = N -> parent ) != NULL );
// (do while)-ループの終了
削除ケース2 カレントノードN が新しい根となる。すべての経路から1つの黒ノードが削除されたので、RB性質は維持される。木の黒高さは1減少する。
// Case_D2 (P == NULL):
return ; // 削除完了
削除ケース3 兄弟ノードS は赤だから、P とおいのC とD は黒でなければならない。P でdir-回転S がN の祖父母ノードになる。そして、P とS の色を反転させても、N を通る経路は黒ノードが1つ少ないままである。しかし、N は赤の親P と黒の兄弟S を持っているので、ケースD4、D5、D6の変換で赤黒木の形を復元することができる。
Case_D3 : // Sは赤 && P+C+Dは黒:
RotateDirRoot ( T , P , dir ); // Pは根かもしれない
P -> color = RED ;
S -> color = BLACK ;
S = C ; // != NIL
// ここで: Pは赤 && Sは黒
D = S -> child [ 1 - dir ]; // 遠いおい
if ( D != NIL && D -> color == RED )
goto Case_D6 ; // Dは赤 && Sは黒
C = S -> child [ dir ]; // 近いおい
if ( C != NIL && C -> color == RED )
goto Case_D5 ; // Cは赤 && S+Dは黒
// それ以外のC+Dは黒とみなす。
// Case_D4に該当する。
削除ケース4 兄弟S とS の子どもは黒だが、P は赤である。S とP の色を交換しても、S を通る経路の黒ノードの数には影響しないが、N を通る経路の黒ノードが1つ追加され、削除された黒ノードの分を補うことができる。
Case_D4 : // Pは赤 && S+C+Dは黒:
S -> color = RED ;
P -> color = BLACK ;
return ; // 削除完了
削除ケース5 兄弟S は黒、S のN に近い子C は赤、S のN に遠い子D は黒である。S で(1-dir)-回転C はS の親となり、N の新しい兄弟となる。S とC の色を交換する。どの経路も黒ノードの数は同じだが、N には黒の兄弟があり、その遠い方の子は赤なので、ケースD6に適合するノード群となる。N もその親P もこの変換の影響を受けず、P は赤にも黒にもなる（図中の
Case_D5 : // C red && S+D black:
RotateDir ( S , 1 - dir ); // S is never the root
S -> color = RED ;
C -> color = BLACK ;
D = S ;
S = C ;
// now: D red && S black
// fall through to Case_D6
削除ケース6 兄弟S は黒、S の遠い子D は赤である。P でdir-回転S はP とS の遠い子D の親となる。P とS の色を交換し、D を黒にする。部分木の根は依然として同じ色、すなわち赤か黒（図中の 要件4 が守られる。N を通らない部分木の経路（図中のD とノード3を通る経路）は、以前と同じ数の黒ノードを通るが、N には黒ノードの祖先が1つ追加される。P が黒くなったか、P が黒かったのにS の祖父母が黒くなったか、のどちらかである。したがって、N を通過する経路は、さらに1つの黒ノードを通過するので、要件5 が回復し、全体の木は赤黒木の形になる。
Case_D6 : // Dは赤 && Sは黒:
RotateDirRoot ( T , P , dir ); // Pは根かもしれない
S -> color = P -> color ;
P -> color = BLACK ;
D -> color = BLACK ;
return ; // 削除終了
} // RBdelete2の終了
このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレース である。
脚注 関連項目 外部リンク
「Red–black tree」の例文・使い方・用例・文例 Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
Red–black treeのページの著作権
Weblio 辞書
情報提供元は
参加元一覧
にて確認できます。
