赤黒木

ウィキペディアから無料の百科事典

赤黒木
種類 木構造
発表時期 1972
発明者 en:Rudolf Bayer
ビッグオー記法による計算量 (en) 
アルゴリズム 平均 最悪の場合
空間
探索 [1] [1]
挿入 償却された [2] [1]
削除 償却された [2] [1]

赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。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]

  1. 各ノードは赤か黒の色をもつ。
  2. 根は黒である (この条件はしばし省かれる。根は赤から黒に変えることはできるので、解析にはほとんど影響しない)。
  3. 葉 (NIL) はすべて黒である。葉はすべて根と同じ色である。
  4. 赤のノードは黒ノードを2つ子に持つ（したがって、赤のノードの親ノードは黒である）。
  5. 任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である（この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる）。

これらの条件から、次の赤黒木の重要な性質が導かれる。

  • 根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない。

これは、赤黒木がある程度の平衡性をもっているということである。挿入・削除・検索といった操作は最悪のケースでは木の高さに比例した時間を要するので、このような赤黒木の性質から理論的に最悪時間計算量の見積もりが立つことになる。これは通常の二分探索木と異なる赤黒木の特徴である。

先ほどの条件からなぜ今の性質が導かれるのかを確認するには、条件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 )
Animation of tree rotations taking place.
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 と表される。
  • は赤ノードを、 は（黒高さ ≥ 1 の）非NILの黒ノードを表し、（非NIL）ノード は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。
  • 図には3つの列と2～4つのアクションが含まれる。
    • 左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。[6]
    1. 動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件に違反している。
      カレントノードNは青い枠で囲まれ、他のノードはNとの関係によってラベル付けされている。
    2. 回転が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。
    3. 再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。[7]
    4. まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードNで挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、Nに対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。
      その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。
  • 番号が書かれた黒丸を頂点とする三角形（）は、赤黒木の部分木（要件4に従ってその親に接続）を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。
    番号が書かれた三角形（）は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが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になるという意味で、リバランシングの問題が レベル高い木にエスカレートされる。そのため、木の修復には最大で 回の繰り返しが必要になる（ここで は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。
  • ループの本体から、ケースI1は単独で抜け、ケースI4、I6、I5 + I6、I3への終了分岐がある。
  • 回転はI6とI5 + I6の時にループの外側で発生する。したがって、合計で最大2回の回転が発生する。

挿入ケース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

挿入ケース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

挿入ケース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

挿入ケース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になることで、リバランスの問題が木で レベル高くエスカレートされる。そのため、木の修復には最大で 回の繰り返しが必要になる（ は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。（ただ、余談だが Mehlhorn & Sandersが指摘している。"AVL木は一定の償却更新コストをサポートしない"[3]:165,158これは、削除後のリバランシングには当てはまるが、AVL挿入には当てはまらない。[9]）
  • ループの本体からは、ケースD3、D6、D5 + D6、D4、D2への分岐があり、削除ケース3セクションは、それ自体でケースD6、D5、D4への3種類の分岐がある。
  • D6とD5 ＋ D6とD3 ＋ D5 ＋ D6で回転が発生するが、すべてループの外側である。したがって、最大で合計3回の回転が発生する。
→ 記号の説明
最初の反復
上位の反復
削除ケース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

削除ケース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

削除ケース4[編集]

兄弟SとSの子どもは黒だが、Pは赤である。SとPの色を交換しても、Sを通る経路の黒ノードの数には影響しないが、Nを通る経路の黒ノードが1つ追加され、削除された黒ノードの分を補うことができる。 

Case_D4: // Pは赤 && S+C+Dは黒:   S->color = RED;   P->color = BLACK;   return; // 削除完了
→ 記号の説明
最初の反復
上位の反復
削除ケース5

削除ケース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

削除ケース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の終了

このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。

脚注[編集]

  1. ^ a b c d James Paton. “Red–Black Trees”. 2021年12月22日閲覧。
  2. ^ a b リバラシングのみ (検索は無し)、Tarjan and Mehlhornを参照。
  3. ^ a b c Mehlhorn, Kurt; Sanders, Peter (2008). “7. Sorted Sequences”. Algorithms and Data Structures: The Basic Toolbox. Berlin/Heidelberg: Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf 
  4. ^ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). “13. Red–Black Trees”. Introduction to Algorithms (3rd ed.). MIT Press. pp. 308–309. ISBN 978-0-262-03384-8 
  5. ^ Tarjan, Robert Endre (April 1985). “Amortized Computational Complexity”. SIAM Journal on Algebraic and Discrete Methods 6 (2): 306–318. doi:10.1137/0606031. http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf. 
  6. ^ a b 左の列は右の列よりはるかに少ないノードしか含まず、特に削除の場合はそうである。これは、挿入と削除のリバランシングループから最初の反復を引き出すことで、ある程度の効率を得られることを示している。なぜなら、名前付きノードの多くは最初の反復ではNILノードであり、後で決定的に非NILノードとなるからである。（この章のコメントを参照.）
  7. ^ わかりやすくするために、回転は再色付けの前に行われる。しかし、この2つのアクションは可換であるため、回転を末尾に行うことも自由である。
  8. ^ a b Ben Pfaffでも同じような分割が見られる。
  9. ^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2

関連項目[編集]

外部リンク[編集]

その他
配列構造(英)
リンク構造(英)
検索構造(英)
木構造
二分木
平衡二分木
B木
トライ木
BSP木
R木
多重木
ヒープ
グラフ構造
抽象データ型
「https://ja.wikipedia.org/w/index.php?title=赤黒木&oldid=98988462」から取得