2-3木
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木の場合、内部ノードのキーと一致した場合はどの子供を検索するかを、あらかじめ決めておく必要がある（以降のパターンでは同じ値の場合、より右の子供を検索するとする）。
操作
検索
2-3木の検索は以下のように行われる。
- 根を対象ノードとして検索を開始する
- 検索対象のノードが葉であり、検索値と一致するなら検索成功として終了、検索値と一致しないなら木に登録されていないものとして終了する
- 検索対象の内部ノードのキーが一つの場合、検索値がキーより小さいなら左へ大きいなら右のノードを次の対象とする。
- 検索対象の内部ノードのキーが二つの場合、検索値2つのキーどちらよりも小さいなら左へ、片方のキーより大きくもう片方のキーより小さいなら真ん中へ、どちらよりも大きい場合は右のノードを次の対象とする
- 2.以下を繰り返す。
BB木の場合はこれに、内部ノードのキーに一致した場合に検索成功として返す処理が加わる。2-3木は根から葉までの距離が全て等しいため、要素数を N とすると検索に要する実行時間 2-3木、BB木共に O (log N) に比例する。2分探索木と異なりこの時間は、データの順序によって劣化することはない。
挿入
挿入の操作は2-3木の場合は具体的には以下のようになる。
- 検索と同様の操作を行って葉の一つ上の親を検索する。
- その親に挿入値を挿入する。
- もし、挿入値を挿入した場合に、子供が3つになった場合は、親のキーを変更する。キーの値は一番左の子供の値と、真ん中の子供の値になる。
- もし、挿入値を挿入して子供が 4つになった場合は、親のノードを、子供を二つもつノード二つに分割する。分割した親ノードのキーおよび分割の仕方は挿入値とノードの状態によって異なる（右図参照）
- 2以降の処理を親の分割が行われなくなるまで、繰り返す。
BB木の場合も同様にまず葉の部分に追加要素を追加する。追加する位置がにすでに要素が2つにある場合は中央値をとり、それを親とする2ノードを形成し、根から葉の全ての距離が一致するように親の分割と、回転を行うことで実装される（詳しくはB木を参照）。
削除
削除の処理は2-3木とBB木でかなり異なる。2-3木の場合は以下の様になる
- 削除する要素を持つ親が3つの子供を持つ場合は、その要素を削除して、親のキーを更新する。削除値が兄弟の中でもっとも大きい場合は、親のキーから削除値と同じキーを削除する。削除値が兄弟の中で真ん中の場合、親のキーから自分の値を削除して右の兄弟を真ん中に移動する。一番左の場合は真ん中の兄弟のキーを削除して真ん中を左へ右を真ん中へ移動する。
- 削除する要素を持つ親が2つの子供を持つ場合、親の兄弟を検索する。
- 検索した親の兄弟が2つの子供を持つ場合は親とその兄弟を、3つの子供を持つ1つの親に併合する。
- 3.の操作で併合された場合、親のそのまた親の子供の数が 2.か 3.であることを確認し、1つである場合は、2以降の処理を繰り返す。
BB木の場合はまず、削除値を削除して、2-3木の条件を満たすかを判断する。もし削除値が2つの要素をもつ葉なら、その値を削除するだけでよい。それ以外の場合は削除後に親との中央値を算出し、もし子供が足りなくなったら親の兄弟と併合を繰り返すことで実装される。
参考文献
- A.エイホ・J.ホップクロフト・J.ウルマン著、『アルゴリズムの設計と解析I』、野崎昭弘・野下浩平訳、サイエンス社、1977年、ISBN 4-7819-0279-0
- N.ヴィルト著、『アルゴリズムとデータ構造』、浦昭二・国府方久史訳、近代科学社、1990年、ISBN 4-7649-0162-5
