2-3木

提供: ORWiki
2007年7月12日 (木) 23:43時点における122.17.2.240 (トーク)による版 (新しいページ: '【にーさんぎ (2-3 tree)】 平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパス...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【にーさんぎ (2-3 tree)】

平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパスの長さも同じ, という2つの条件を満たす. 2-3木ではすべてのデータは葉に記憶される. 頂点数 $n$ の2-3木は, 再平衡化により, 要素の挿入・削除・ある要素が含まれるかの確認を O$(\log n)$ 時間で行う. また, 再平衡化と似た技法により, 任意の位置での木の分割・2つの木の合併を O$(\log n)$ 時間で行う.