「2-3木」の版間の差分
(新しいページ: '【にーさんぎ (2-3 tree)】 平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパス...') |
|||
| 1行目: | 1行目: | ||
【にーさんぎ (2-3 tree)】 | 【にーさんぎ (2-3 tree)】 | ||
| − | 平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパスの長さも同じ, という2つの条件を満たす. 2-3木ではすべてのデータは葉に記憶される. 頂点数 | + | 平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパスの長さも同じ, という2つの条件を満たす. 2-3木ではすべてのデータは葉に記憶される. 頂点数 <math>n\,</math> の2-3木は, 再平衡化により, 要素の挿入・削除・ある要素が含まれるかの確認を O<math>(\log n)\,</math> 時間で行う. また, 再平衡化と似た技法により, 任意の位置での木の分割・2つの木の合併を O<math>(\log n)\,</math> 時間で行う. |
2007年7月13日 (金) 02:42時点における版
【にーさんぎ (2-3 tree)】
平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパスの長さも同じ, という2つの条件を満たす. 2-3木ではすべてのデータは葉に記憶される. 頂点数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\,} の2-3木は, 再平衡化により, 要素の挿入・削除・ある要素が含まれるかの確認を O構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\log n)\,} 時間で行う. また, 再平衡化と似た技法により, 任意の位置での木の分割・2つの木の合併を O構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\log n)\,} 時間で行う.