読み方：あかくろぎ

赤黒木【red–black tree】

赤黒木とは？

データ構造の一種である木構造の一つで、各ノードに「赤」または「黒」の色を割り当てることで木のバランスを自動的に維持する二分探索木のこと。データの探索や挿入、削除をいずれも最悪でも O（log n）の計算量で実行でき、様々なプログラミング言語の標準ライブラリやオペレーティングシステム（OS）の内部処理に採用されている。

二分探索木は、各ノードの左の子孫に小さい値、右の子孫に大きい値を配置する二分木で、高速な検索を実現することができる。しかし、データの挿入順によっては木が一方に偏り、最悪の場合は連結リストと同等の構造になる。この状態では計算量が O（n）まで悪化する。赤黒木はこの偏りを防ぐために色情報と再調整の仕組みを組み込んだ構造である。

赤黒木が満たすべき条件は厳密に定められている。根ノードは黒でなければならず、赤いノードの子ノードは必ず黒である。また、任意のノードから葉ノードまでのすべての経路において、通過する黒いノードの数が等しくなければならない。この条件により、木の高さが 2log（n+1）以下となることが数学的に保証される。

挿入や削除の際にこれらの条件が崩れた場合、ノードの色の変更と「回転」と呼ばれる部分的な親子関係の組み替えを組み合わせて条件を回復する。修復処理は O（log n）の手順で完了するため、操作全体の計算量は維持される。同じく平衡二分探索木の一種である「AVL木」は探索性能に優れる一方、更新時の調整が多くなる場合がある。赤黒木は平衡条件をやや緩やかに設定することで更新処理の負荷を抑えており、検索と更新の双方が頻繁に発生する用途に適している。

1972年にルドルフ・バイヤー（Rudolf Bayer）が考案した「対称二分B木」を起源とし、1978年にレオニダス・ギバス（Leonidas J. Guibas）とロバート・セジウィック（Robert Sedgewick）によって現在の形に整理された。C++言語の標準テンプレートライブラリ（STL）に含まれる「std::map」や「std::set」、Javaの「Tree Map」、Linuxカーネルのタスクスケジューラ「CFS」（Completely Fair Scheduler）における処理キューなどで実装されている。