「赤黒木」の版間の差分
ナビゲーションに移動
検索に移動
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | ''' | + | '''【 あかくろぎ (red black tree) 】''' |
| − | + | 平衡二分探索木の一種で，(1) すべての頂点は赤か黒，(2) 赤い頂点は必ず黒い親をもつ，(3) 根とすべての葉は黒，(4) 根から葉へのどのパスも同数の黒い頂点を含む，という4つの条件を満たす．この条件より，根から葉へのどのパスも，長さが2倍以上違わなくなり，ゆえに要素数<math>n \, </math>の赤黒木の高さは<math>\mathrm{O}(\log n) \,</math>になる．赤黒木は，木の形の変化に対して再平衡化を行うことにより，要素の挿入・削除・ある要素が含まれるかの確認を<math> \mathrm{O}(\log n) \,</math>で実行できる． | |
2007年9月22日 (土) 14:52時点における最新版
【 あかくろぎ (red black tree) 】
平衡二分探索木の一種で，(1) すべての頂点は赤か黒，(2) 赤い頂点は必ず黒い親をもつ，(3) 根とすべての葉は黒，(4) 根から葉へのどのパスも同数の黒い頂点を含む，という4つの条件を満たす．この条件より，根から葉へのどのパスも，長さが2倍以上違わなくなり，ゆえに要素数の赤黒木の高さはになる．赤黒木は，木の形の変化に対して再平衡化を行うことにより，要素の挿入・削除・ある要素が含まれるかの確認をで実行できる．
