2-3木を徹底解説：構造・操作・実装上の注意と応用（ITエンジニア向け深掘りコラム）
エバープレイ編集部はじめに — 2-3木とは何か
2-3木（2-3 tree）は、自己平衡な探索木の一種で、B木（B-tree）の特殊ケース（次数3のB木）にあたります。各内部ノードは2つの子または3つの子を持ち、各ノードは1個または2個のキーを保持します。重要な性質は「すべての葉が同じ深さにある」ことで、これにより木の高さが厳密に制限され、探索・挿入・削除の最悪計算量が対数時間に保たれます。本稿では2-3木の構造、操作（挿入・削除）、実装上の注意、他のデータ構造との比較、実際の応用や並行処理・永続化への応用までを詳しく解説します。
構造と基本性質
ノードの型：各ノードは1つまたは2つのキー（区切り値）を持ち、それに応じて2つまたは3つの子ポインタを持ちます（葉は子を持ちません）。
葉の深さの同一性：全ての葉は同じ深さに存在する（完全平衡）。これが高さの上限を厳格にする点で重要です。
高さの境界：葉の個数Lについて、2^h ≤ L ≤ 3^h が成り立ちます。したがってノード数nに対する高さhはおおよそ log_3(n) ≤ h ≤ log_2(n) となり、探索はO(h)=O(log n)です。
順序性：各ノード内のキーは昇順に並び、子ポインタはそれぞれキーの大小関係に従う区間を担当します（通常のB木と同様）。
探索（検索）のアルゴリズムと計算量
探索はルートから葉へ降りる標準的なB木型の処理で、各ノードで1または2個のキーを比較して次の子を選びます。したがって1ノードあたりの比較数は定数で、木の高さに比例する比較を行うため、時間計算量はO(h)=O(log n)です。実装上はノード内のキーを配列で保持し、線形探索（1〜2比較）か二分探索（小さな配列では線形の方が実際は速い）を使います。
挿入操作の詳細（分割を伴うアップデート）
挿入基本手順は次の通りです。
1) 挿入すべきキーの葉ノードを探索して到達する。
2) その葉にキーを挿入する。葉が1キーのみであれば、2キーにして終了。
3) もし葉がすでに2キーで、さらに1つ挿入して3キーになってしまうときは「分割」を行う。中央のキーを親へ昇格（プロモート）し、左右に1キーずつの2つのノードに分割する。
4) 親にキーを挿入することで親が3キーになれば、同じく分割を親に対して行い、この処理は根に達するまで伝播する可能性がある。根が分割されれば新しい根ができ、木の高さが1増える。
挿入の計算量は葉までの探索O(log n)に加え、分割伝播が最悪O(h)回発生するので合計O(log n)です。実装上は分割時に新しいノードの割り当てとポインタの更新が必要で、メモリアロケーションのコストに注意します。
削除操作の詳細（借用と結合）
削除は挿入よりやや複雑です。概念的には次の手順をとります。
1) 木から削除するキーを探す。キーが内部ノードにある場合は、通常、直前（あるいは直後）の葉ノードのキーで置き換え（置換）して、実際の削除は葉から行う。これにより葉のみの下位操作に帰着できる。
2) 葉からキーを削除した結果、その葉ノードが0キー（許容最小は1キー）になったら「アンダーフロー」が発生する。
3) アンダーフローの修正方法は次のいずれか：
- 隣接する兄弟ノードからキーを借りる（兄弟に2キーがあれば、親から区切りキーを1つ下ろして再配分する）。
- 借用できない場合は兄弟と結合（マージ）し、親の区切りキーを降ろして1つのノードにまとめる。これにより親がキーを失い、親でアンダーフローが起こる可能性があるため修正が上方へ伝播する。
4) 根でアンダーフローが起きて子が1つしか残らない場合、根を縮めて高さを1つ下げる（現在の根を廃止し、その唯一の子を新しい根とする）。
削除処理も最悪O(log n)の時間で完了します。実装では兄弟との再配分や結合時のポインタ更新に慎重さが必要です。
例：挿入と分割の具体イメージ（図がない場合の説明）
例えば空の木に順にキー 10, 20, 30 を挿入すると、初めは10を根の葉に置く。20を入れると同じ葉に2キー(10,20)になる。30の挿入で葉が3キーになったため分割が必要。中央の20が親へ昇格し、左右に10と30の2つの葉ができる。親がなければ20が新しい根となり高さが1増加する。
実装上の注意点と最適化
ノード表現：固定長配列（最大2キー、3ポインタ）を持つ構造体にするのが単純で高速。キー数を別フィールドで管理し、キー配列を部分的に詰めて保持する。
メモリ管理：頻繁な分割・結合でノード割り当てが多くなるため、オブジェクトプールやスラブアロケータを用いるとGC/アロケーションのオーバーヘッドを下げられる。
イテレータ実装：葉を双方向リンクで連結しておくと順次走査が高速。インオーダーでの反復は通常のDFSでも可能だが、葉連結は実用的利点が大きい。
キー比較：キーが複雑型の場合は比較回数を減らす工夫（キーの先頭フィールドでの早期判定など）をする。ノード内比較は定数回だが頻繁に呼ばれる。
2-3木と他の平衡木との比較
B木系：2-3木は次数が小さいB木で、ディスクやページ指向の用途では一般に大きな次数（例えば100や1000）を持つB+木の方が好適。2-3木はメモリ内での教育用・理論解析向けに使われやすい。
2-3-4木（2-3-4 tree）：各ノードが2〜4つの子を持てるB木の一種で、赤黒木（red-black tree）との1対1の対応が知られている。赤黒木は2-3-4木を二分木にエンコードしたものと見なせる。
AVL木・赤黒木：AVL木は高さ差を厳格に制御しており検索が最速に近いが回転が頻繁。赤黒木は緩やかな平衡条件で実装が比較的単純で、ライブラリ実装（例えばJavaのTreeMap）で広く使われる。2-3木自体は内部ノードに複数キーを持つため回転より分割・結合で平衡を保つ点が異なる。
実用面：メモリ・キャッシュ効果やノードサイズの点で、実運用ではB+木や赤黒木が選ばれることが多い。2-3木は理論理解や教育、特定の用途（各ノードが少数のキーを持つことでメリットがある場合）で有用。
応用例と適用場面
教育・理論研究：2-3木は「平衡を保つための分割・結合」という概念を分かりやすく示すため教材に適している。
小規模メモリ内辞書：ノードが小さく、一定の並列走査が容易なため、用途によっては単純で高速に振る舞う。
持続的データ構造の基盤：永続化（不変データ構造）を目指す場合、ノードの部分コピー（パスコピー）によりバージョン管理がしやすい構造である。
永続化（関数型データ構造）と並行処理への応用
関数型言語での永続2-3木は、挿入・削除時に影響を受けるノードのみを新規コピーし、残りを共有する実装が可能です。この場合、各更新はO(log n)の新しいノード割り当てを伴いますが、過去バージョンへのアクセスが一定コストで可能になります。並行処理では、ノード単位のロック（ロックカップリング）や楽観的並行制御が適用できます。特に細粒度ロックやトランザクショナルメモリを用いることで高並列性を狙えますが、分割・結合の発生時に複雑なロック順序が必要になるため設計は慎重に行う必要があります。
実装の落とし穴と注意点
ルートの特別扱い：根ノードは最小キー数が0でも許容されるなど特別ケースがある。根が空になると高さを下げる処理を忘れると木の整合性が崩れる。
借用と結合の間違い：兄弟ノードがどちらにあるかで再配分の実装が異なる。隣接兄弟から借用する場合の親キーの移動方向に注意すること。
メモリリーク・ダングリングポインタ：結合で古いノードを廃棄する際、参照が残ると深刻なバグになる。ガベージコレクションがない言語では解放ミスに注意。
まとめ
2-3木はB木の一種として理論的に美しく、分割と結合により高さを厳密に制御することで常にO(log n)の操作性能を保証します。実装は概念的に単純ですが、分割・結合・親子ポインタ更新などでの細かなケース分けが必要で、実運用ではB+木や赤黒木が選ばれることが多いです。本稿で示した挿入・削除のアルゴリズム、実装上の最適化、並行性と永続化に関する指針は、2-3木を用いる／理解するうえで実践的な助けになるはずです。
参考文献
投稿者プロフィール
