翻訳と辞書
Words near each other
・ 二色の浜公園
・ 二色の浜海水浴場
・ 二色の独楽
・ 二色パン
・ 二色二順
・ 二色刷り
・ 二色型色覚
・ 二色型色覚者
・ 二色性
・ 二色性色覚
二色木
・ 二色浜駅
・ 二荒 (列車)
・ 二荒山
・ 二荒山滝右エ門
・ 二荒山瀧右エ門
・ 二荒山神社
・ 二荒神社
・ 二荒芳之
・ 二荒芳徳


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

二色木 : ウィキペディア日本語版
赤黒木[あかくろぎ]

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



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.