自己平衡木とは何か？AVL・赤黒木・Splay・Treap・B木の特徴と使い分けガイド
エバープレイ編集部自己平衡木とは — 基本概念
自己平衡木（じこへいこうぎ、self-balancing tree）は、データ構造の一種で、挿入・削除などの操作によって木の高さが極端に大きくならないように自動的に形を調整（平衡化）する二分探索木の総称です。目的は主に探索・挿入・削除などの各操作を平均的に O(log n) の時間で保証することで、最悪ケースでの線形時間化（退化してリスト状になること）を防ぐことにあります。
なぜ必要か
普通の二分探索木（BST）は挿入順序次第で偏り、最悪で高さが n になり、探索が O(n) になってしまいます。自己平衡木はバランス条件と再構成（回転など）によって高さを制約し、性能の安定化を図ります。
多くの実用的なソフトウェア（データベースのインデックス、言語ランタイムのマップ実装、OS のデータ構造など）で、常に安定した対数時間性能が求められるため採用されます。
代表的な自己平衡木の種類
AVL木：1962 年に Adelson-Velsky と Landis によって提案。各ノードに高さやバランス係数（左右部分木の高さ差）を持ち、高さ差が常に −1〜+1 に保たれるように回転（単回転・二重回転）で調整します。探索が速く（厳密な高さ制約）、検索優先の用途に向きますが、挿入・削除時の回転や高さ更新がやや多くなりがちです。
赤黒木（Red–Black Tree）：各ノードに「赤・黒」の色を持たせることでバランスを維持します。赤黒木は高さが AVL より緩く抑えられるため、挿入・削除の平均コストが比較的少なく、標準ライブラリの実装（例：Java の TreeMap や C++ の map の多くの実装）に採用されることが多いです。赤黒木は最悪でも O(log n) の検索を保証します。
Splay木：操作対象のノードを根に「スプレー」して移動させる自己調整木。定常的にアクセスされる要素を高速にする「ワーキングセット性」を持ち、各操作の摂動後のコストは最悪では O(n) ですが、系列操作に対しては「振幅平均（amortized）O(log n）」を保証します。実装が比較的簡潔で、キャッシュ局所性が良い場合があります。
Treap（トレープ）：二分探索木とヒープの性質を同時に満たすランダム化データ構造。各ノードにランダムな優先度を割り当て、BST のキー順とヒープ性を満たすように回転で保ちます。期待時間で O(log n) を達成するため、理論的解析が比較的簡潔です。
B木・B+木：外部記憶（ディスク）向けにノードあたり多数の子ポインタを持たせ、高い扇形度で高さを小さくする木です。自己平衡木の派生的な考え方で、データベース・ファイルシステムのインデックスで広く使われます。
平衡を保つ基本手法（回転と再色付け）
多くの自己平衡二分探索木は「局所操作（回転）」を用いて構造を修正します。回転は O(1) 時間で親子関係を入れ替え、部分木の高さや重心を改善します。
単回転（Left/Right Rotation）：片側に偏った部分を回転で持ち上げる操作。AVL の単回転や赤黒木のケースで用います。
二重回転（Left-Right / Right-Left）：まず子側で回転してから親側で回転する 2 段階の回転。AVL の特定の不均衡ケースで必要になります。
色の変更と回転（赤黒木）：赤黒木では色を変える（赤→黒、黒→赤）ことで局所的バランスを修正し、必要に応じて回転を行います。これにより黒高（root から葉までの黒いノード数）が保たれます。
各種木の特性比較（概観）
AVL：高さがより厳密に抑えられるため、検索が最速級。挿入・削除時に回転が多くなる傾向。
赤黒木：平均的に良い性能バランス。実装はやや複雑だが、挿入・削除が安定。標準ライブラリで多用。
Splay：短期的な連続アクセスに強い（ローカリティ最適化）。最悪単一操作はコスト高だが振幅平均は良好。
Treap：ランダム性に依存するが実装が比較的単純で期待性能が保証される。
B木系（B-tree / B+tree）：ディスクアクセス最小化に有利。データベースやファイルシステム向け。
計算量（時間・空間）
探索・最小/最大・前後関係の取得：多くの自己平衡木で O(log n)（最悪または期待／振幅平均）。
挿入・削除：AVL・赤黒木で O(log n)（最悪）。Splay は amortized O(log n)、単一操作は最悪 O(n)。Treap は期待 O(log n)。
空間オーバーヘッド：各ノードに親ポインタ、色ビットや高さ情報（AVL）などの追加データが必要。実装により若干の差があるが概して O(n) の補助情報。
実装上の注意点
境界ケースの取り扱い：空木や片側のみの部分木などで回転・再色処理を適切に行う必要があります。
再帰 vs 反復：深い再帰を用いる実装は n が大きいとスタックオーバーフローの恐れがあるため、反復ベースの実装や明示的スタックを検討します。
単体テスト：挿入・削除の組合せで invariants（AVL の高さ差制約、赤黒木の色条件や黒高さなど）が常に成り立つかを検査するテストが重要です。
用途と選び方のガイドライン
メモリ内の汎用ソート済みキーのマップ：赤黒木（標準ライブラリの実装）や AVL が代表例。検索が中心なら AVL、更新が多ければ赤黒木が適することが多い。
短時間に同じキーへ繰り返しアクセスするワークロード：Splay 木はワーキングセットに応じて効果的。
外部記憶（ディスク/SSD）を意識する場合：B木 / B+木 を検討（ノード幅を大きくして I/O を削減）。
並列・並行アクセス：ロック分割や細粒度ロック、あるいはロックフリー構造の研究が必要。自己平衡操作は局所的だが、回転は親子ポインタを直接変更するため注意が必要です。
発展的トピック
持続化（Persistence）: 永続データ構造としての自己平衡木は、変更前のバージョンを保持する用途に有用。部分的に共有することで履歴管理やタイムトラベルが可能。
ランダム化と競合回避：Treap のようなランダム化手法は、最悪ケースを確率的に回避するアプローチです。
実装最適化：ポインタレイアウト、メモリプール、バイト単位での圧縮（色ビットをポインタの空きビットに埋め込む）などを用いることで高速化・メモリ効率化が可能です。
まとめ
自己平衡木は、探索・更新を安定的に高速化するための重要なデータ構造群です。用途やワークロードによって AVL、赤黒木、Splay、Treap、B木など適切な実装を選ぶことが重要で、それぞれがトレードオフ（検索速度 vs 更新コスト、メモリオーバーヘッド、外部記憶最適化など）を持ちます。実装時は不変条件（invariants）と回転・再調整ロジックを厳密に扱い、テストやベンチマークで想定ワークロードに対する性能を確認することを推奨します。
参考文献
- 自己平衡二分探索木 - Wikipedia（日本語）
- AVL木 - Wikipedia（日本語）
- 赤黒木 - Wikipedia（日本語）
- Splay木 - Wikipedia（日本語）
- Treap - Wikipedia（English）
- B木 - Wikipedia（日本語）
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms（参考書）
- Java Platform SE 8 - TreeMap（実装参考：赤黒木）
- Linux Kernel rbtree Documentation（実装例）
投稿者プロフィール
