2-3木

2-3木 (2-3 tree) とは

2-3木は、計算機科学におけるデータ構造で、特に平衡木（balanced tree）に分類される木構造の一種です。この木構造は、データ検索、挿入、削除などの操作を効率的に行うために設計されています。

定義

2-3木には、要素の持ち方に関して文献によっていくつかのバリエーションがありますが、共通する定義は以下の通りです。

内部ノードの構造: すべての内部ノードは、2つまたは3つの子を持ちます。1つ以下、または4つ以上の子を持つ親ノードは存在しません。
葉の深さ: すべての葉は、根からの距離が等しくなっています。これは、木が平衡を保つための重要な特性です。
内部ノードのキー: 内部ノードは、1つまたは2つのキーを持ちます。
1つのキーを持つノードは、2分探索木と同様に、そのキーよりも小さい子を左に、大きい子を右に格納します。
2つのキー（a, b、ただし a < b）を持つノードは、aよりも小さい子を左に、aよりも大きくbよりも小さい子を中央に、bよりも大きい子を右に配置します。

2-3木には、要素の持ち方に関して大きく分けて2つのパターンが存在します。

1. 葉にのみ要素を持つパターン: すべての葉が1つの要素を持ち、内部ノードのキーは要素とはなりません。このパターンでは、すべての要素は葉に格納されます。
2. 内部ノードも要素を持つパターン: 内部ノードのキー自体が要素であり、葉も2つの要素を持つことができます。このパターンは、特にオーダーが3のB木の操作に類似しており、2分B木（BB木; Binary B-tree）とも呼ばれることがあります。

このドキュメントでは、特に断りがない限り、前者のパターン（葉にのみ要素を持つパターン）を2-3木と呼び、後者のパターンをBB木と呼ぶことにします。

操作

検索

2-3木の検索は、以下の手順で行われます。

1. 根ノードを対象ノードとして検索を開始します。
2. 検索対象のノードが葉であり、検索値と一致する場合、検索は成功として終了します。一致しない場合は、木に登録されていないものとして終了します。
3. 検索対象が内部ノードで、キーが1つの場合、検索値がキーよりも小さければ左の子を、大きければ右の子を次の対象ノードとします。
4. 検索対象が内部ノードで、キーが2つの場合、検索値が2つのキーどちらよりも小さければ左の子を、片方のキーよりも大きくもう片方のキーよりも小さければ真ん中の子を、どちらよりも大きければ右の子を次の対象ノードとします。
5. 上記の手順を繰り返します。

BB木の場合は、上記の処理に加えて、内部ノードのキーに一致した場合に検索成功とする処理が追加されます。

2-3木は、根から葉までの距離が常に等しいため、要素数をNとしたとき、検索に必要な実行時間はO(log N)に比例します。この時間は、データの順序によって劣化することがありません。

挿入

2-3木への挿入操作は、以下の手順で行われます。

1. 検索と同様の操作で、挿入対象の要素が属するべき葉の親ノードを特定します。
2. 親ノードに挿入値を挿入します。
3. 挿入により、親ノードの子が3つになった場合、親ノードのキーを更新します。キーの値は、真ん中の子の値と、一番右の子の値になります。
4. 挿入により、親ノードの子が4つになった場合、親ノードを2つの子を持つ2つのノードに分割します。分割された親ノードのキーと分割の方法は、挿入値とノードの状態によって異なります。
5. 親ノードの分割がなくなるまで、上記の手順を繰り返します。

BB木の場合も同様に、まず葉の部分に追加要素を追加します。追加位置にすでに2つの要素がある場合は、中央値を取り、それを親とする2つのノードを形成し、根から葉までのすべての距離が一致するように親の分割と回転操作を行います。

削除

2-3木の削除操作は、以下の手順で行われます。

1. 削除する要素を持つ親ノードが3つの子を持つ場合、その要素を削除し、親ノードのキーを更新します。
削除値が兄弟の中で最も大きい場合、親ノードのキーから削除値と同じキーを削除します。
削除値が兄弟の中で真ん中の場合、親ノードのキーから自分の値を削除し、右の兄弟を真ん中に移動します。
削除値が一番左の場合、真ん中の兄弟のキーを削除し、真ん中を左へ、右を真ん中へ移動します。
2. 削除する要素を持つ親ノードが2つの子を持つ場合、親ノードの兄弟を検索します。
3. 検索した兄弟ノードが2つの子を持つ場合、親ノードとその兄弟ノードを、3つの子を持つ1つの親ノードに併合します。
4. 手順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

関連項目

2-3-4木
B木
AVL木
赤黒木

もう一度検索