赤黒木

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ウィキメディア・コモンズには、赤黒木 に関連するカテゴリがあります。

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

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

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

[編集] 用語

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

子を持たないノードを、木のこずえにあたることから葉という。また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。赤黒木においては、葉は「空（nil）」、すなわち値をもたないノードとする。

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

そのノードの右部分木に含まれるノードのもつ値より大きくない
そのノードの左部分木に含まれるノードのもつ値より小さくない

という性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。

[編集] 用途と利点

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

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

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

[編集] 性質

赤黒木の例。「NIL」は空の葉。

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

各ノードは赤か黒の色をもつ。
根は黒である。
葉はすべて黒である。（したがって、赤のノードは子をもつ。）
赤のノードの子ノードはすべて黒である。（したがって、対偶より、赤のノードの親ノードもすべて黒である。）
どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である。（この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる。）

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

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

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

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

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

ところで、赤黒木について、二分木の（ノードではなく）辺に色がついたものであるという説明がなされていることもある。これは、この記事における「ノードの色」を「ノードとその親とを連結する辺の色」に読み替えたものである（ただし、「根ノードの色」に対応するものはないため、この記事での条件2にあたる条件が不要となる）。