赤黒木

赤黒木は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。

このデータ構造は1972年のルドルフ・ベイヤー  の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス  とロバート・セジウィック  によって発表された論文による。

赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がOと短く、複雑ではあるが実用的なデータ構造として知られている。

この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版に掲載されている。

1. 用語
-----

赤黒木は二分木の一種であり、コンピュータ科学においてテキストの断片や数などの比較可能なデータを組織化する際に用いられる。データは二分木のノードに配置され、そのうちでスタート地点となる「どのノードの子でもないノード」を根という。根は2つまでの「子」をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も……、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。

赤黒木に置ける葉はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなくヌルポインタで表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。

赤黒木は二分探索木であり、すなわち、各ノードのもつ値が

そのノードの右部分木に含まれるノードのもつ値より大きくない
そのノードの左部分木に含まれるノードのもつ値より小さくないという性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。

ノードの黒深さは、根からそのノードまでの黒ノードの数と定義される。赤黒木の黒高さは、根から葉までのどの経路にもある黒のノードの数であり、要件5により一定である。  ノードの黒高さは、そのノードが根とする部分木の黒高さである。この記事では、NILノードの黒高さは0とする。なぜなら、その部分木は図2が示唆するように空であり、その木の高さも0であるからである。

2. 用途と利点
--------

赤黒木というデータ構造は、最悪のケースにおける計算量が、データの挿入・削除・検索のいずれにおいても、データ構造のうちで最善のものの一つである。このため、リアルタイム・コンピューティングのような時間計算量に敏感なアプリケーションにおいて有益である。また、計算幾何学で用いるデータ構造など、最悪のケースでの計算量を保証する必要のあるデータ構造の基礎としても有用なことが多い。 赤黒木と同様に平衡二分木であるAVL木は、赤黒木に比べて平衡性についての条件が厳しく、そのためAVL木では最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。

赤黒木は関数型プログラミングにおいても部分的に重要であり、永続的データ構造を実現するデータ構造の一つとして、変更後も以前の値を保持し続けるような連想配列や集合を実装する際に広く用いられるものの一つである。なお、このような永続性をもったタイプの赤黒木では、挿入や削除のたびに、時間だけでなく のオーダーの空間が必要となる。

赤黒木は2-3-4木にアイソメトリックである。すなわち、任意の2-3-4木に対して、少なくとも一つの赤黒木でその2-3-4木と同じデータを同じ順序でもつものが存在する。このとき、2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作に等価であり、そのため、2-3-4木を考えることは赤黒木の背景にある理論を理解する上で重要である。実用性の高くない2-3-4木が、アルゴリズムの入門書において赤黒木の直前によく紹介されているのは、このためである。

3. 性質
-----

赤黒木は、各ノードに「赤」または「黒」という「色」をつけた二分探索木であり、赤黒木として有効なものであるためには、通常の二分探索木としての条件のほか、以下の条件が要求される。

各ノードは赤か黒の色をもつ。
根は黒である 。
consideredBlack}}葉  はすべて黒である。葉はすべて根と同じ色である。
req4}}赤のノードは黒ノードを2つ子に持つ。
req5}}任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である。これらの条件から、次の赤黒木の重要な性質が導かれる。

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

先ほどの条件からなぜ今の性質が導かれるのかを確認するには、条件4からわかる「赤黒木の根から葉までの道において赤のノードが2つ続くことはない」という性質がカギになる。すなわち、条件をみたす最短の道というのはすべて黒のノードからなる道であり、条件を満たす最長の道というのは赤と黒のノードが交互に現れるような道となる。そして、条件5より、根から葉までの道がすべて同じ個数の黒のノードを含むことから、最長の道の長さは最短の道の長さの二倍を超えないという上記の性質が導かれる。

一般に、データの木構造 による表現では、ノードが一つだけの子をもつことや、葉ノードがデータをもつことを可能としている場合も多い。赤黒木においてもそのような考え方を導入することができないわけではないが、それをすると先ほどの性質をいくつかの点で修正する必要が生じ、またアルゴリズムが複雑になってしまう。そのため、この記事においては、今まで説明したように「空の葉」を用い、葉はデータをもたずただ木の終端を意味するだけのノードであるとした。なお、このような葉ノードは図をかく際には省略することも多く、その結果、赤黒木が先ほどの条件をみたさないように見えることがある。しかしもちろん、実際には内部のノードはすべて、空の葉を含めて2つの子をもっているわけである。

ところで、赤黒木について、二分木の辺に色がついたものであるという説明がなされていることもある。これは、この記事における「ノードの色」を「ノードとその親とを連結する辺の色」に読み替えたものである。

4. アプリケーションと関連するデータ構造
---------------------

赤黒木は挿入時間、削除時間、探索時間において、最悪のケースを保証する。これはリアルタイムシステムのような時間センシティブなアプリケーションにおいて価値あるのみならず、最悪のケースを保証する他のデータ構造における価値ある部品となっている。 例えば、計算幾何学で用いられる多くのデータ構造は赤黒木をベースとしているし、現行のLinuxカーネルで用いられる CFS では赤黒木を使用している。

AVL木は の探索、挿入、削除をサポートする、もう一つのデータ構造である。AVL木は、赤黒木よりも厳密な平衡性を持っているため、挿入や削除は遅くなるが、検索は早くなる。このため、AVL木は一度構築して、再構成する必要のないデータ構造にとっては魅力的である。例えば、言語辞書などのように。

また、赤黒木はAVL木よりも条件が多いため、実装が面倒である。

赤黒木はまた、最も一般的な永続データ構造のひとつであり、関数型言語で特に価値がある。変化後に前のバージョンを保持できるように、連想配列や集合 を構築するのに使われる。赤黒木の永続バージョンは、各挿入や各削除において の空間を要する。

5. 操作
-----

すべての赤黒木は単純な二分探索木の特殊なケースであるため、赤黒木に対する探索や木の走査などの読み取り専用操作は、二分探索木で使われるものと何の変更もない。しかし、挿入や削除の直後は赤黒木の性質に反する場合があるため、これを修復して赤黒木を平衡にすることをリバランシングという。amortized}}操作における最悪時間計算量は、O記法で 、平均では、 または償却された 、色の変更には定数310}} 158}}と小さい数になり、木の回転は3回以内となる。

挿入と削除の操作の詳細は、例としてC++のコードを用いて説明する。サンプルコードでは、以下の型定義とマクロ、および回転のためのヘルパー関数を使用する。

// 基本の型定義:

enum color_t { BLACK, RED };

struct RBnode { // 赤黒木のノード RBnode* parent; // == NULL  RBnode* child[2]; // == NIL  // Index is: // LEFT := 0, if  // RIGHT := 1, if  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 の子方向を取得する

define childDir ->right ? RIGHT : LEFT )<WtXmlEndTag />

RBnode* RotateDirRoot int dir) { // dir ∈ { LEFT, RIGHT } RBnode* G = P->parent; RBnode* S = P->child[1-dir]; RBnode* C; assert; // 真のノードへのポインターを要求する C = S->child[dir]; P->child[1-dir] = C; if  C->parent = P; S->child[ dir] = P; P->parent = S; S->parent = G; if  G->child[ P == G->right ? RIGHT : LEFT ] = S; else T->root = S; return S; // 部分木の新しい根 }
define RotateDir RotateDirRoot
define RotateLeft RotateDirRoot
define RotateRight RotateDirRoot<WtXmlEndTag />

5.1. サンプルコードと挿入図・削除図に関する注記
--------------------------

この提案では、挿入と削除の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。

変数 N はカレントノードを表し、図中では N と表される。
は赤ノードを、 は非NILの黒ノードを表し、ノード は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。
図には3つの列と2～4つのアクションが含まれる。
左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。
動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件に違反している。
カレントノードNは青い枠で囲まれ、他のノードはNとの関係によってラベル付けされている。
回転が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。
再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。
まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードNで挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、Nに対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。
その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。
番号が書かれた黒丸を頂点とする三角形は、赤黒木の部分木を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。
番号が書かれた三角形は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが0になる。

コメント 簡単のため、サンプルコードでは論理和と U == NIL || U->color == BLACK //// 黒とみなす// 論理積を U != NIL && U->color == RED   //// 黒でないとみなす// 使用する。 そのため、U == NIL の場合、論理和・論理積ともに式全体が評価されないことに留意する必要がある。この場合、どちらの場合も U->colorは評価されない。
(黒とみなすというコメントは、要件2に準じたものである。）