|
2-3木（-き）とは計算機科学におけるデータ構造で特に平衡木（balanced tree）に属する木構造の一種である。 == 定義 == 画像:2-3-4 tree 2-node.svg|子供を2つもつノード。aより小さいノードが p、大きいノードが qになる。 画像:2-3-4-tree 3-node.svg|子供を3つもつノード。aより小さいノードが p、aより大きく bより小さいノードが q、bより大きいノードが r になる。 2-3木は後述する様に要素の持ち方に関して文献によって違いがあるが、共通する定義として、 * すべての内部ノードは 2か3の子供を持つ（1つ、または4つ以上の子供を持つ親は存在しない） * 全ての葉は根からの距離が等しい（平衡木） * 内部ノードは1つか2つのキーを持つ。 * 1つのキーを持つノードは2分探索木と同様に、そのキーより小さい子供を左に大きい子供を右に格納している。 * 2つのキー（a, bで a < b とする）を持つノードは、a より小さい子供を左に、a より大きく b より小さい子供を真ん中に、b より大きい子供を右に配置する。 という木構造である。2-3木は特に要素の持ち方に関しては文献によって違いがあり、大きく分けて二つのパターンがある。一つは全ての葉は一つだけ要素を持ち、内部ノードのキーは要素とならない（すなわち全ての要素は葉に格納される）パターンである。もう一つは内部ノードのキー自体が要素であり、葉も2つの要素を持つことができるパターンである。後者のパターンは特にオーダーを 3にしたB木の操作と同様であり、このパターンを指して2分B木（BB木; Binary B-tree）という呼び方をすることもある。この項でも便宜上、2-3木と呼ぶ場合は主に前者のパターンを指し、後者のパターンはBB木と呼ぶことにする。なお前者のパターンの2-3木の場合、内部ノードのキーと一致した場合はどの子供を検索するかを、あらかじめ決めておく必要がある（以降のパターンでは同じ値の場合、より右の子供を検索するとする）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「2-3木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 2-3 tree 」があります。 スポンサード リンク
|