|
赤黒木
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nは木の要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。 この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree)に掲載されている。 用語赤黒木の例  図1: 明示的な葉(NIL)を持つ赤黒木  図2: 左右の暗黙のドッキングポイントを持つ赤黒木 赤黒木は二分木の一種であり、コンピュータ科学においてテキストの断片や数（例:図1や図2の数値）などの比較可能なデータを組織化する際に用いられる。データは二分木のノードに配置され、そのうちでスタート地点となる「どのノードの子でもないノード」を根という。根は2つまでの「子」（根に接続しているノード）をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も……、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。 赤黒木における葉（図1の NIL ）はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなくヌルポインタで表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。 赤黒木は二分探索木であり、すなわち、各ノードのもつ値が
という性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。 ノードの黒深さは、根からそのノードまでの黒ノードの数（すなわち黒祖先の数）と定義される。赤黒木の黒高さは、根から葉までのどの経路にもある黒のノードの数であり、要件5により一定である（代わりに、任意の葉のノードの黒深さとして定義することもできる）。 [3]:154–165 ノードの黒高さは、そのノードが根とする部分木の黒高さである。この記事では、NILノードの黒高さは0とする。なぜなら、その部分木は図2が示唆するように空であり、その木の高さも0であるからである。 用途と利点赤黒木というデータ構造は、最悪のケースにおける計算量が、データの挿入・削除・検索のいずれにおいても、データ構造のうちで最善のものの一つである。このため、リアルタイム・コンピューティングのような時間計算量に敏感なアプリケーションにおいて有益である。また、計算幾何学で用いるデータ構造など、最悪のケースでの計算量を保証する必要のあるデータ構造の基礎としても有用なことが多い。 赤黒木と同様に平衡二分木であるAVL木は、赤黒木に比べて平衡性についての条件が厳しく、そのためAVL木では最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。 赤黒木は関数型プログラミングにおいても部分的に重要であり、永続的データ構造を実現するデータ構造の一つとして、変更後も以前の値を保持し続けるような連想配列や集合を実装する際に広く用いられるものの一つである。なお、このような永続性をもったタイプの赤黒木では、挿入や削除のたびに、時間だけでなく のオーダーの空間が必要となる。 赤黒木は2-3-4木にアイソメトリックである。すなわち、任意の2-3-4木に対して、少なくとも一つの赤黒木でその2-3-4木と同じデータを同じ順序でもつものが存在する。このとき、2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作に等価であり、そのため、2-3-4木を考えることは赤黒木の背景にある理論を理解する上で重要である。実用性の高くない2-3-4木が、アルゴリズムの入門書において赤黒木の直前によく紹介されているのは、このためである。 性質赤黒木は、各ノードに「赤」または「黒」という「色」をつけた二分探索木であり、赤黒木として有効なものであるためには、通常の二分探索木としての条件のほか、以下の条件が要求される。[4]
これらの条件から、次の赤黒木の重要な性質が導かれる。
これは、赤黒木がある程度の平衡性をもっているということである。挿入・削除・検索といった操作は最悪のケースでは木の高さに比例した時間を要するので、このような赤黒木の性質から理論的に最悪時間計算量の見積もりが立つことになる。これは通常の二分探索木と異なる赤黒木の特徴である。 先ほどの条件からなぜ今の性質が導かれるのかを確認するには、条件4からわかる「赤黒木の根から葉までの道において赤のノードが2つ続くことはない」という性質がカギになる。すなわち、条件をみたす最短の道というのはすべて黒のノードからなる道であり、条件を満たす最長の道というのは赤と黒のノードが交互に現れるような道となる。そして、条件5より、根から葉までの道がすべて同じ個数の黒のノードを含むことから、最長の道の長さは最短の道の長さの二倍を超えないという上記の性質が導かれる。（ここで、根と葉は黒のノードである。） 一般に、データの木構造 (データ構造)による表現では、ノードが一つだけの子をもつことや、葉ノードがデータをもつこと（言い換えれば、データをもつノードが子をもたないこと）を可能としている場合も多い。赤黒木においてもそのような考え方を導入することができないわけではないが、それをすると先ほどの性質をいくつかの点で修正する必要が生じ、またアルゴリズムが複雑になってしまう。そのため、この記事においては、今まで説明したように「空の葉」（nil leaf、null leaf）を用い、葉はデータをもたずただ木の終端を意味するだけのノードであるとした。なお、このような葉ノードは図をかく際には省略することも多く、その結果、赤黒木が先ほどの条件をみたさないように見えることがある。しかしもちろん、実際には内部の（つまり、葉ではない）ノードはすべて、空の葉を含めて2つの子をもっているわけである。 ところで、赤黒木について、二分木の（ノードではなく）辺に色がついたものであるという説明がなされていることもある。これは、この記事における「ノードの色」を「ノードとその親とを連結する辺の色」に読み替えたものである（ただし、「根ノードの色」に対応するものはないため、この記事での条件2にあたる条件が不要となる）。 アプリケーションと関連するデータ構造赤黒木は挿入時間、削除時間、探索時間において、最悪のケースを保証する。これはリアルタイムシステムのような時間センシティブなアプリケーションにおいて価値あるのみならず、最悪のケースを保証する他のデータ構造における価値ある部品となっている。 例えば、計算幾何学で用いられる多くのデータ構造は赤黒木をベースとしているし、現行のLinuxカーネルで用いられる CFS （Completely Fair Scheduler）では赤黒木を使用している。 AVL木は の探索、挿入、削除をサポートする。もう一つのデータ構造である、AVL木は、赤黒木よりも厳密な平衡性を持っているため、挿入や削除は遅くなるが、検索は早くなる。このため、AVL木は一度構築して、再構成する必要のないデータ構造にとっては魅力的である。例えば、言語辞書（または、アセンブラやインタープリタの命令コードのようなプログラム辞書）などのように。 また、赤黒木はAVL木よりも条件が多いため、実装が面倒である。 赤黒木はまた、最も一般的な永続データ構造のひとつであり、関数型言語で特に価値がある。変化後に前のバージョンを保持できるように、連想配列や集合 (プログラミング)を構築するのに使われる。赤黒木の永続バージョンは、各挿入や各削除において の（時間に加えて）空間を要する。 操作すべての赤黒木は単純な二分探索木の特殊なケースであるため、赤黒木に対する探索や木の走査などの読み取り専用操作は、二分探索木で使われるものと何の変更もない。しかし、挿入や削除の直後は赤黒木の性質に反する場合があるため、これを修復して赤黒木を平衡にすることをリバランシングという。操作における最悪時間計算量は、O記法で （ は木の要素数）、平均では、 または償却された 、色の変更には定数（実際には非常に速い）[5]:310 [3]:158と小さい数になり、木の回転は3回以内（挿入は2回）となる。 挿入と削除の操作の詳細は、例としてC++のコードを用いて説明する。サンプルコードでは、以下の型定義とマクロ、および回転のためのヘルパー関数を使用する。 // 基本の型定義:
enum color_t { BLACK, RED };
struct RBnode { // 赤黒木のノード
RBnode* parent; // == NULL (木のルートの時)
RBnode* child[2]; // == NIL (子が空の時)
// Index is:
// LEFT := 0, if (key < parent->key)
// RIGHT := 1, if (key > parent->key)
enum color_t color;
int key;
};
#define NIL NULL // ヌルポインタまたは番兵ノードへのポインタ
#define LEFT 0
#define RIGHT 1
#define left child[LEFT]
#define right child[RIGHT]
struct RBtree { // 赤黒木
RBnode* root; // == NIL (木が空の時)
};
// ルートでない非NILの RBnode* N の子方向（∈ { LEFT, RIGHT }）を取得する
#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )
 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つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。
挿入挿入は、新しい（非NIL）ノード（Nとする）を、二分探索木における、間順走査での先行ノードのキーが新しく挿入するノードのキーより小さく、かつ新しく追加するノードのキーが後行ノードのキーより小さくなるNILノードの位置に配置することから始まる。（多くの場合、この位置は、挿入操作の直前に木内を探索した結果であり、ノード 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 {
リバランシングループは以下の不変条件を持つ。
挿入図に関する注記
挿入ケース1カレントノードの親Pは黒であるから、要件4が成立する。ループ不変条件により、要件5も成立する。 if (P->color == BLACK) {
// Case_I1 (Pは黒):
return; // 挿入完了
}
// ここからPは赤
if ((G = P->parent) == NULL)
goto Case_I4; // Pは赤かつ根
// else: Pは赤 そして G!=NULL.
dir = childDir(P); // ノードPが位置するGの側（右か左か）
U = G->child[1-dir]; // おじ
if (U == NIL || U->color == BLACK) // Uが黒とみなされると
goto Case_I56; // Pは赤 && Uは黒
挿入ケース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は 回実行され、木の合計高さが1増加し、現在 となる。カレントノードNは木の（赤）根であり、すべての赤黒木の性質が満たされている。 // (do while)ループを抜ける(Case_I2から抜け出した後)。
// Case_I3: Nは根であり、赤。
return; // 挿入完了
挿入ケース4親Pは赤で根。Nも赤なので、要件4に違反する。しかし、Pの色を変えると、木は赤黒木の形になり、木の黒高さが1つ増える。 Case_I4: // Pは根かつ赤:
P->color = BLACK;
return; // 挿入完了
挿入ケース5親Pは赤だが、おじUは黒。最終的な目標は、親ノードPを祖父母の位置に回転させることだが、NがGの内側の孫の場合（つまり、NがGの右子の左子またはGの左子の右子の場合）、これはうまくいかない。Pで 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で // 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が黒
リバランシングループは以下の不変条件を持つ。
削除図に関する注記
削除ケース1P、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で 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で 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で Case_D6: // Dは赤 && Sは黒:
RotateDirRoot(T,P,dir); // Pは根かもしれない
S->color = P->color;
P->color = BLACK;
D->color = BLACK;
return; // 削除終了
} // RBdelete2の終了
このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。 脚注
関連項目外部リンク
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
