探索木の基礎と主要型の比較：BST・AVL・赤黒木・B木・Trie の特徴と適用ガイド
エバープレイ編集部探索木とは — 概要
探索木（たんさくぎ、search tree）は、キー（値）を木構造で保持し、探索（検索）、挿入、削除などの操作を効率よく行えるように設計されたデータ構造の総称です。各ノードにキーが格納され、ノード間の関係（子・親）はキーの大小関係に基づく制約を満たします。代表的な特徴として、木をたどることでキーを順序付けされて扱えるため、範囲検索や順序付き走査（in-order traversal）にも適しています。
探索木の基本ルールと主要操作
もっとも基本的な探索木は「二分探索木（BST: Binary Search Tree）」です。BSTでは任意のノードに対し、左部分木の全キーはそのノードのキーより小さく、右部分木の全キーは大きい（等号の扱いは重複の方針による）という不変条件を持ちます。
- 検索（search）: 根から辿り、比較により左か右へ進む。平均・最良では O(log n)（平衡なら）、最悪は O(n)。
- 挿入（insert）: 葉位置に新しいノードを追加。BSTの性質を維持する。
- 削除（delete）: 葉、片方の子、両方の子を持つ場合で処理が異なる。後者は後続（in-order successor）などで置換して削除。
- 走査（traversal）: 中間順（in-order）で辿るとソートされたキー列が得られる。
主要な探索木の種類と特徴
探索木には用途や実装性能に応じた多くの派生があります。主要なものを概説します。
二分探索木（BST）
最も単純で理解しやすい形。再帰やイテレーションで実装されますが、データが偏ると片側に寄った「退化」したリスト状になり、探索や更新が O(n) になります。
AVL木（AVL tree）
1972年にAdelson-VelskyとLandisによって提案された自己平衡二分探索木。任意のノードについて左右部分木の高さ差（バランス因子）が -1、0、+1 の範囲に保たれるよう回転（rotation）で再構築します。これにより高さは O(log n) に抑えられ、検索・挿入・削除が最悪ケースでも O(log n) です。AVLは回転がやや多めになる一方、検索が頻繁な用途で高速を発揮します。
赤黒木（Red–Black tree）
赤黒木は色（赤／黒）を各ノードに付与して木の特性を保つ自己平衡木です。AVLほど厳密ではない平衡条件のため、挿入・削除の手続きが平均的に少し簡潔であり、実用上の定数因子が小さいため多くの標準ライブラリ（例：C++の std::map、Javaの TreeMap）で採用されています。理論上の高さは 2·log2(n+1) を上回らないことが知られています。
B木・B+木（B-tree / B+tree）
B木はディスクやデータベース向けに設計された多分岐木です。各ノードが複数キーと複数子ポインタを持ち、ノード1個がディスクブロックに対応することで入出力（I/O）回数を削減します。ノードあたりのキー数には下限・上限があり、挿入・削除時に分割・併合を行って高さを制御します。B+木はすべての実データ（レコード参照）を葉に持ち、葉が双方向リストでつながれているため範囲検索に特に有利です。
トライ木（Trie、接頭辞木）
キーが文字列などの配列である場合に使われる木で、各エッジが文字を表します。キー長 L に対して検索は O(L)（木の高さに依存）です。共通接頭辞を1回だけ格納できるため、オートコンプリートや辞書実装、IPルーティングテーブルなどに有用ですが、ノード数が増えるとメモリ消費が大きくなる点に注意が必要です。圧縮トライ（Patricia trie など）でメモリを削減する工夫があります。
その他 — サフィックスツリー／サフィックス配列
文字列検索に特化した構造としてサフィックスツリーやサフィックス配列があります。これらは全ての接尾辞を扱うことで、最長共通部分列やパターン検索を高速に行えます。構築アルゴリズム（Ukkonen など）は線形時間での構築が可能です。
高さ制御（バランス）と回転操作
自己平衡二分木では「回転（rotation）」により局所的に構造を変え、高さを制御します。基本的な回転は左回転と右回転の2種類で、AVLや赤黒木の修復手順はこれらを組み合わせます。回転は部分木の再配置のみで行われるため、計算量は定数時間です。
計算量（時間・空間）まとめ
- 未平衡BST: 平均検索 O(log n)、最悪 O(n)
- AVL / 赤黒木（平衡BST）: 検索・挿入・削除いずれも O(log n)（最悪保証あり）
- B木: ノード訪問回数は O(log_t n)（tは最小次数）、ディスクI/Oを低減
- Trie: キー長を L とすると検索 O(L)、空間はアルファベットサイズに依存
- メモリ: ポインタ／子配列の数に依存。トライはメモリコストが高い傾向。
実装上の注意点・工夫
- 重複キーの扱い: マルチセットにするか、カウントを持つか、リストで保持するかを明確にする。
- 再帰とスタックオーバーフロー: 深い木では再帰による実装がスタックを圧迫するため反復実装やループでの実装を検討。
- メモリとキャッシュ効率: ポインタだらけのノードはキャッシュミスを招く。配列ベースやノードプール、B木的なブロック配置で改善できる。
- 永続化（不変データ構造）: 関数型プログラミングではノード共有により過去状態を保持できる永続探索木が使われる。
- 並列・ロック: 高並列環境ではロックフリー／細粒度ロックの探索木設計（例: lock-free BST、concurrent skip list）が求められる。
実用的な選択ガイド
- 汎用用途（ライブラリ、マップ）: 赤黒木や平衡二分木が標準的。
- ディスク／DBのインデックス: B木／B+木が適切（ブロック単位のI/Oを最小化）。
- 文字列の前方一致検索・オートコンプリート: トライや圧縮トライ。
- 高頻度の検索と稀な更新: AVLのような厳密な平衡が有利な場合がある。
まとめ
探索木は「キーを順序付けて効率的に管理する」ための基本的かつ重要なデータ構造群です。単純な二分探索木から、自己平衡木（AVL・赤黒木）、ディスク指向のB木、文字列向けのトライまで用途に応じたバリエーションが存在します。選択のポイントは「検索頻度」「更新頻度」「メモリ制約」「I/O 特性」「キーの性質（数値か文字列か）」であり、これらを踏まえて適切な木を選ぶことが性能向上の鍵です。
参考文献
- Binary Search Tree — Wikipedia
- AVL tree — Wikipedia
- Red–black tree — Wikipedia
- B-tree — Wikipedia
- Trie — Wikipedia
- Ukkonen's algorithm — Wikipedia (suffix tree construction)
- Introduction to Algorithms (Cormen et al.) — 概説（書籍）
投稿者プロフィール
