赤黒木

【 あかくろぎ (red black tree) 】

平衡二分探索木の一種で，(1) すべての頂点は赤か黒，(2) 赤い頂点は必ず黒い親をもつ，(3) 根とすべての葉は黒，(4) 根から葉へのどのパスも同数の黒い頂点を含む，という4つの条件を満たす．この条件より，根から葉へのどのパスも，長さが2倍以上違わなくなり，ゆえに要素数$n\,$の赤黒木の高さは$\mathrm {O} (\log n)\,$になる．赤黒木は，木の形の変化に対して再平衡化を行うことにより，要素の挿入・削除・ある要素が含まれるかの確認を$\mathrm {O} (\log n)\,$で実行できる．