赤黒木

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