「赤黒木」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
'''【あかくろぎ (red black tree)】'''
+
'''【 あかくろぎ (red black tree) 】'''
  
平衡二分探索木の一種で, (1) すべての頂点は赤か黒, (2) 赤い頂点は必ず黒い親をもつ, (3) 根とすべての葉は黒, (4) 根から葉へのどのパスも同数の黒い頂点を含む, という4つの条件を満たす. この条件より, 根から葉へのどのパスも,  長さが2倍以上違わなくなり, ゆえに要素数 $n$ の赤黒木の高さは O($\log n$)になる. 赤黒木は, 木の形の変化に対して再平衡化を行うことにより, 要素の挿入・削除・ある要素が含まれるかの確認を O$(\log n)$ で実行できる.
+
平衡二分探索木の一種で,(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倍以上違わなくなり,ゆえに要素数の赤黒木の高さはになる.赤黒木は,木の形の変化に対して再平衡化を行うことにより,要素の挿入・削除・ある要素が含まれるかの確認をで実行できる.