C/C++で学ぶ2-3木（2-3ツリー）とは？検索と挿入のアルゴリズムを徹底解説

2-3木（2-3ツリー）とは

2-3木（2-3ツリー）とは、子を持つすべてのノード（内部ノード）が、「1つのデータ要素と2つの子（2ノード）」または「2つのデータ要素と3つの子（3ノード）」のいずれかを持つ木構造のデータ構造として定義されます。

定義

内部ノードが1つのデータ要素と2つの子を持つ場合、そのノードを「2ノード」と呼びます。

内部ノードが2つのデータ要素と3つの子を持つ場合、そのノードを「3ノード」と呼びます。

以下のいずれかの条件を満たすとき、かつそのときに限り、Tは2-3木であると言えます。

• Tが空であること。言い換えれば、Tはノードを一切含みません。

• Tがデータ要素aを持つ2ノードであること。Tに左の子Lと右の子Rが存在する場合、次の条件が成り立ちます。

• LとRは、同じ高さを持つ空でない2-3木として扱われる。

• aはL内の各要素よりも大きい。

• aはR内の各データ要素以下である。

• Tがデータ要素aとb（a < b）を持つ3ノードであること。Tに左の子L、中央の子M、右の子Rが存在する場合、次の条件が成り立ちます。

• L、M、Rは、同じ高さを持つ空でない2-3木として扱われる。

• aはL内の各データ要素よりも大きく、M内の各データ要素以下である。

• bはM内の各データ要素よりも大きく、R内の各データ要素以下である。

2-3木の性質

• すべての内部ノードは、2ノードまたは3ノードとして扱われます。

• すべての葉は同じレベル（深さ）に位置します。

• すべてのデータはソートされた順序で保持されます。

操作

検索（Searching）

2-3木における要素の検索は、二分探索木における検索とほぼ同じ考え方で行われます。各ノード内のデータ要素は順序付けられているため、検索処理は正しい部分木へと導かれ、最終的に目的の要素を含む正しいノードにたどり着きます。

• Tを2-3木、dを検索したいデータ要素とします。Tが空の場合、dはTに存在せず、処理は終了です。

• rをTの根（ルート）とします。

• rが葉である場合、dがrに存在しなければdはTにも存在しません。そうでなければ、dはTに存在します。特に、dは葉ノードで見つかるため、これ以上の手順は不要となり、処理は終了です。

• rが左の子Lと右の子Rを持つ2ノードであるとします。eをr内のデータ要素とします。

ここで、考慮すべきケースは3つあります。

• dがeと等しい場合：dがTの中で見つかったので、処理は終了です。

• dがeより小さい場合：TをLに設定します。Lは定義により2-3木であるため、ステップ2に戻って処理を続けます。

• dがeより大きい場合：TをRに設定し、ステップ2に戻ります。

• rが左の子L、中央の子M、右の子Rを持つ3ノードであるとします。aとbをrの2つのデータ要素（a < b）とします。この場合、考慮すべきケースは4つあります。

  • dがaまたはbと等しい場合：dはTに存在するので、処理は終了です。

  • dがaより小さい場合：TをLに設定し、ステップ2に戻ります。

  • aがdより小さく、dがbより小さい場合：TをMに設定し、ステップ2に戻ります。

  • dがbより大きい場合：TをRに設定し、ステップ2に戻ります。

挿入（Insertion）

挿入は、まずキーの適切な位置を検索し、その場所にキーを追加することで行われます。追加によってノードが4ノードになった場合には、そのノードを2つの2ノードに分割し、中央のキーを親ノードへ移動させます。親ノードも4ノードになる可能性があり、その場合は同様に分割が行われ、キーがさらに上の親へと伝播していきます。このプロセスは、分割の必要がない2ノードの親に到達するまで繰り返され、根に到達した場合には、伝播してきた要素を使って新しい根（2ノード）を作成します。

このアルゴリズムでは、必要な操作回数は木の高さに比例します。木は完全にバランスが取れているため、計算量は対数時間（O(log n)）になります。また、このプロセスによって結果が必ず2-3木となることが保証されており、特にすべての葉は同じ深さに保たれます。

下の図は、このプロセスで起こりうるケースを示したものです。

2-3木への数値の挿入における3つの可能なケース。