赤黒木（Red-Black Tree, RBT）の紹介
- 2019年11月27日
- Liu, An-Chi 劉安齊
¶ 赤黒木の概要
赤黒木（Red-Black Tree）は特殊なデータ構造で、AVL 木と同様に自動で平衡を保つ機能を持ちます。
赤黒木には以下の性質があります：
- 各ノードは黒または赤のどちらか
- 根（root）は黒
- すべての葉（leaf）は
NILであり黒 - あるノードが赤なら、その子はすべて黒
- root から leaf までの各パスに含まれる黒ノード数は等しい
これらの規則に従うことで、ノードの挿入や削除を行っても木の平衡状態を保てます。赤黒木は、ノード数が n のとき木の高さが最大でも 2log(n+1) を超えないことが保証されます。
現実世界では集合（set）や辞書（dictionary）の実装に使われることが多く、C++ の std::set や std::map は内部的に赤黒木で実装されています。