2-3木（2-3ツリー）とは？C++で学ぶデータ構造とアルゴリズムの基礎

2-3木とは

2-3木（2-3ツリー）は、データ構造における木構造の一種で、すべての内部ノードが「2ノード」または「3ノード」のいずれかで構成される平衡木です。次数3のB木（B-Tree）の特殊な形と考えることができます。

2ノードとは、データを1つ持ち、子ノードを2つ持つノードのことです。

3ノードとは、データを2つ持ち、子ノードを3つ持つノードのことです。

図：2-3木の例

2-3木の性質

• すべての内部ノードは、2ノードまたは3ノードのいずれかである。
• データを1つ持つノードは、子をちょうど2つ持つ2ノードか、子を持たない葉ノードのどちらかである。
• データを2つ持つノードは、必ず子をちょうど3つ持つ3ノードとなる。
• すべての葉ノードは常に同じ深さ（レベル）に存在する。
• 2-3木は常に高さがバランスした木（高さ平衡木）である。
• データが整列して管理されているため、検索操作が高速かつ効率的に行える。

2ノードの特徴

• 子ノードを正確に2つ持つ。
• 左の子は親のデータより小さい値を持つ。
• 右の子は親のデータより大きい値を持つ。
• 子を持たない葉ノードになることもある。

3ノードの特徴

• 子ノードを正確に3つ持つ。
• データ値を2つ持つ。
• 左の子は左側のデータ値より小さい値を持つ。
• 中央の子は2つのデータ値の間に収まる値を持つ。
• 右の子は右側のデータ値より大きい値を持つ。
• 決して葉ノードにはならない。

2-3木に対する主な操作

1. 検索

• データが整列されているため、二分探索木の検索操作とよく似ている。
• 2-3木から値Xを検索する手順は以下の通り。
• 木が空の場合 → 「見つからない（False）」を返す。
• 根ノードまで到達しても見つからない場合 → Falseを返す。
• Xが左側のデータより小さい場合は、左部分木を探索する。
• Xが左側のデータより大きく、右側のデータより小さい場合は、中央部分木を探索する。
• Xが右側のデータより大きい場合は、右部分木を探索する。

2. ノードの挿入

• 2-3木に値Xを挿入する手順は以下の通り。
• 木が空の場合 → Xを根ノードとして追加する。
• Xの適切な位置を検索し、葉ノードとして追加する。
• データを1つだけ持つ葉ノードがある場合 → そこにXを追加すると、そのノードは2ノードになる。
• 葉ノードがすでに2つのデータを持っている場合 → Xを仮の3ノードとして追加し、ソート順に従ってデータを親ノードへ移しながらノードを分割する。

例：10, 5, 8, 15, 23, 21 の順にノードを追加して2-3木を構築してみましょう。

3. ノードの削除

• 2-3木から値Xを削除する手順は以下の通り。
• 木が空の場合はFalseを返す。
• Xの位置を検索して削除し、その後木全体を調整する。
• Xが3ノードの一部である場合 → Xを削除し、残った左の値と中央の値を調整する。必要に応じて祖先ノードの左と中央の値も調整する。
• Xが2ノードの一部である場合 → 再帰的に木を調整・分割し、ノードをソート順に再配置する。

まとめ

2-3木は、常に高さのバランスが保たれるため、最悪の場合でも検索・挿入・削除をO(log n)の時間計算量で実行できる強力なデータ構造です。赤黒木など他の平衡探索木の理論的基礎にもなっており、C++での実装を通じてB木系データ構造への理解を深めるのに最適な題材といえます。