赤黒木
ウィキペディア フリーな encyclopedia
赤黒木(あかくろぎ)は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。
概要 赤黒木, 種類 ...
赤黒木 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
種類 | 木構造 | ||||||||||||||||||||
発表時期 | 1972 | ||||||||||||||||||||
発明者 | en:Rudolf Bayer | ||||||||||||||||||||
ビッグオー記法による計算量 (en) | |||||||||||||||||||||
|
閉じる
このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。
赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)(nは木の要素数)と短く、複雑ではあるが実用的なデータ構造として知られている。
この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree)に掲載されている。