赤黒木平衡条件

赤黒木平衡条件は、赤黒木という自己平衡二分探索木が常に対数時間での検索・挿入・削除を保証するために満たすべき規則の集合である。赤黒木は各ノードに赤または黒の色を付与し、根が黒であること、赤ノードの子は必ず黒であること、任意のノードからその子孫の葉（NIL）までの黒ノード数が全て同じであること、外部葉は黒とみなす、といった条件を課すことで、木の高さが最悪でも2倍以下に抑えられ、操作の計算量がO(log n)に収まるようになる。これによりデータベースやファイルシステムのインデックスなど、リアルタイム性が求められる領域で広く利用されている。