平衡探索木の完全ガイド：AVL・赤黒木・Splay・Treap・B木の特徴と実装の選択ポイント
エバープレイ編集部平衡探索木とは — 概要
平衡探索木（へいこうたんさくぎ、balanced search tree）は、探索・挿入・削除などの操作を効率的に行うために、木構造の高さ（深さ）がある条件で制限されるように設計された探索木（主に二分探索木や多分木）の総称です。高さが制限されることで、最悪ケースでも操作の計算量を対数オーダー（O(log n)）に抑えられ、性能の予測可能性が向上します。
なぜ“平衡（バランス）”が重要か
単純な二分探索木はデータの挿入順序によっては偏り、線形リストに近い形（高さが O(n)）になり得ます。これでは探索や更新が最悪 O(n) になり、パフォーマンスが劣化します。平衡探索木は木の高さを O(log n) に保つことで、探索・挿入・削除を効率的に行い、スケーラブルな性能を実現します。
主要な平衡探索木の種類（概要と特徴）
AVL木 — 非常に厳密に高さを管理する二分探索木。各ノードは左右部分木の高さ差（バランス因子）が -1, 0, +1 に保たれる。検索は非常に高速（比較回数が少ない）が、挿入・削除時に再平衡の回転が多くなることがある。高さは最小に近い。
赤黒木（Red-Black Tree） — ノードに色（赤/黒）を持たせることで木の黒高さを制御する二分探索木。AVLより緩やかな平衡条件を持ち、挿入・削除での回転が少なめ。最悪高さは 2·log2(n+1) 以内と知られる。C++の std::map や Java の TreeMap、Linux カーネルの rb-tree 等でよく使われる。
Splay木 — アクセスしたノードを根に“そろばん式”に回転（splaying）して移動させる自己調整木。単一操作の最悪時間は O(n) だが、任意の操作列に対しては振る舞いが良く、各操作の償却時間（amortized）は O(log n)。局所性の高いアクセスに強い。
Treap（ランダム化BST） — 各ノードにランダムな優先度を割り当て、二分探索木かつヒープ性を満たす木。期待計算量は O(log n)。実装が比較的簡潔でランダム化により平均性能が保証される。
2-3木 / 2-3-4木 / AA木 / スケープゴート木（Scapegoat）など — 様々な設計目標（実装の容易さ、回転回数削減、メモリ効率など）に応じたバリエーションが存在する。スケープゴート木は再構築を使って平衡を保ち、回転を使わない代わりに再構築コストを負う。
B木 / B+木 — ディスクやキャッシュを前提にした多分木。各ノードが多数の子を持つ（ノード内に複数のキーを格納）ことで高さを極端に低くし、ブロック読取回数を減らす。データベースやファイルシステムで広く使用される。B+木は内部ノードにキーのみ、葉ノードに全データを保持し、レンジクエリが高速。
平衡の操作（回転と再構成）の基本
多くの平衡二分探索木では、挿入や削除により局所的に条件が破られた場合、回転（rotation）と呼ばれる操作で局所再構成を行います。主なもの：
単回転（single rotation） — 一方向の偏りを直す際に使う。AVLや赤黒木で一般的。
二重回転（double rotation） — 子孫の偏りが逆向きの場合に使用（AVL の LR / RL）。
色反転と回転（赤黒木） — ノードの色を変更しつつ、必要に応じ回転を行って黒高さなどの条件を回復する。
splay 操作（Splay木） — zig / zig-zig / zig-zag というパターンで連続回転を行い、アクセスノードを根に持ってくる。
計算量の見積もり
AVL木・赤黒木・Treap・B木（ノード内キー数を m とする） — 検索・挿入・削除は O(log n)（B木は高さが O(log_m n））。赤黒木は最悪ケースでも O(log n) が保証される。AVL はより厳密な高さ制約で検索が速いが、更新コストはやや高い。
Splay木 — 個々の操作は最悪 O(n) の場合があるが、任意の長い操作列では各操作の償却時間が O(log n)。局所的なアクセスの偏りがある場合に有利。
実運用での定数係数 — 同じ O(log n) でも、ノードあたりのメタ情報（親ポインタ、色ビット、子配列など）や回転回数の差で実行時間に差が出るため、用途に応じた選択が重要。
どの平衡木を選ぶべきか（用途別アドバイス）
メモリ内で高速なランダムアクセスが主目的 — AVL は検索が速く、読み出し中心のワークロードに向く。実装はやや複雑。
汎用的なマップ実装（ライブラリ） — 赤黒木は挿入・削除のオーバーヘッドが少なく実装が安定しているため多用される（C++ std::map, Java TreeMap など）。
ディスク・SSD 上での大規模データ/データベース — B木 / B+木。ノードをディスクブロックに合わせることで I/O を低減できる。レンジスキャンが多い場合は B+木 が有利。
局所性の高いアクセスやキャッシュ効率 — Splay 木は最近アクセスしたデータが速く返ってくる特性を持つ。B+木 はブロックアクセスを圧縮できるため I/O とキャッシュ効率に優れる。
並列・並行アクセス — 通常の平衡二分木はロック制御が難しい。データベース等では B-link 木やロックフリー構造、または skip list（平衡木の代替）を利用することが多い。
実装上の注意点とトレードオフ
メモリオーバーヘッド — 各ノードが持つポインタや色ビット、キーと値の格納形態によりメモリ使用量が変わる。B木ではノード内に配列を持つためオーバーヘッドは増えるが高さは低くなる。
キャッシュ局所性 — 多分木（B木/B+木）はノード内に多くのキーを詰められるためメモリ/ディスクの局所性が良く、実際の速度で優れることが多い。
操作の安定性と予測可能性 — 赤黒木や AVL は最悪ケース保証があり、リアルタイム性が要求される場面で有利。splayは長期的に平均は良いが単発操作で遅くなる可能性がある。
デバッグと保守性 — AVL は回転ケースが多く実装が複雑。赤黒木の方が実装が比較的扱いやすく、ライブラリ実装が豊富。
実世界での利用例
データベースやファイルシステム：B木/B+木（例：InnoDB の一部実装や多くのRDBMS/ファイルシステム）
標準ライブラリの連想配列：C++ std::map（一般的に赤黒木実装）、Java TreeMap（赤黒木）
OSカーネルのデータ構造：Linux カーネルは rb-tree を内部データ構造として使用
キャッシュ・局所性活用：splay 木はアクセス局所性の高い用途で検討されることがある
まとめ
平衡探索木は、データ構造設計における基本であり、用途に応じた選択が重要です。メモリ内での高速検索を重視するのか、ディスクI/Oを最小化するのか、並行性を優先するのかで最適解は変わります。赤黒木や AVL、B木/B+木、splay 木、treap などの特徴を理解し、アクセスパターン・ハードウェア特性・実装コストを踏まえて選ぶことが成功の鍵です。
参考文献
- Balanced tree — Wikipedia
- AVL tree — Wikipedia
- Red–black tree — Wikipedia
- Splay tree — Wikipedia
- Treap — Wikipedia
- B-tree — Wikipedia
- B+ tree — Wikipedia
- std::map — cppreference.com
- Java Platform SE 8 — TreeMap
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms（参考書）
投稿者プロフィール
