赤黒木

出典: ORWiki

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

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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E8%B5%A4%E9%BB%92%E6%9C%A8" より作成