赤黒木（Red-Black Tree）とは？データ構造の特徴とAVL木との違いを解説

この記事では、自己平衡型二分探索木の一つである赤黒木（Red-Black Tree）について解説します。赤黒木は、各ノードに「赤」または「黒」の色情報を持たせることで、木のバランスを自動的に保つデータ構造です。

赤黒木が満たすべき条件

赤黒木では、すべてのノードが以下の性質を満たす必要があります。

• 各ノードは必ず「赤」または「黒」のいずれかの色を持つ
• 根（ルート）ノードは常に黒である
• 赤いノードが隣接して連続することはない（赤ノードの子は必ず黒）
• 任意のノードからその子孫のNULLノードまでのすべての経路には、同じ数の黒ノードが含まれる（これを「黒高さ」と呼びます）

赤黒木の例

以下は、上記の条件を満たす赤黒木の例です。各ノードの色付けによって、木全体の高さが最悪の場合でも約2倍以内に抑えられ、検索・挿入・削除をO(log n)の計算量で実行できます。

葉にNULLノードを含む赤黒木

赤黒木の理論では、実際の葉の下に仮想的なNULLノード（外部ノード）を置いて考えることが一般的です。このNULLノードを含めることで、「根から葉までの経路における黒ノード数が等しい」という条件が厳密に定義されます。

AVL木との比較

AVL木は赤黒木よりもバランスが厳密に保たれているため、検索性能はわずかに優れています。しかし、その反面、挿入や削除の際により多くの回転操作が必要になるという欠点があります。

一方、赤黒木はバランスの制約が緩やかなため、挿入・削除時の回転回数が少なくて済みます。そのため、データの追加や削除が頻繁に行われる場面では、赤黒木の方が総合的なパフォーマンスに優れています。実際、C++のstd::mapやJavaのTreeMapなど、多くの標準ライブラリでも赤黒木が採用されています。