|
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー (:en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log ''n'')（''n''はツリーの要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。 この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree )に掲載されている。 == 用語 == 赤黒木は二分木の一種であり、コンピュータ科学において数などの比較可能なデータを組織化する際に用いられる。データは二分木のノードに配置され、そのうちでスタート地点となる「どのノードの子でもないノード」を根という。根は2つまでの「子」（根に接続しているノード）をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も……、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。 赤黒木に置ける葉はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなくヌルポインタで表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。 赤黒木は二分探索木であり、すなわち、各ノードのもつ値が * そのノードの右部分木に含まれるノードのもつ値より大きくない * そのノードの左部分木に含まれるノードのもつ値より小さくない という性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「赤黒木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Red-black tree 」があります。 スポンサード リンク
|