平衡木の完全ガイド：AVL木・赤黒木・B木・B+木・Splay木・Treap の特徴と実装・用途の選び方
エバープレイ編集部はじめに — 「平衡木」とは何か
平衡木（へいこうぎ、balanced tree）は、二分探索木やその派生構造において「木の高さを低く保つ」ための追加条件（平衡条件）を持つデータ構造群の総称です。平衡が保たれていることで、探索・挿入・削除などの操作を最悪ケースでも対数時間（O(log n)）で保証でき、性能の安定性が向上します。ここでは代表的な平衡木の種類、内部動作（回転や再構成）、計算量、用途や実装上の注意点まで幅広く解説します。
平衡木の基本概念
二分探索木（BST）は各ノードが「左部分木の鍵 < ノードの鍵 < 右部分木の鍵」という順序性を維持しますが、挿入順序次第で木が偏り高さが O(n) になる可能性があります。平衡木はこの偏りを抑えるため、各ノードに追加情報（高さ・色・優先度など）を持たせ、挿入・削除時に局所的な操作（回転や色反転など）を行うことで平衡性を保ちます。
代表的な平衡木の種類
AVL木
1962年にAdelson‑VelskyとLandisが提案。各ノードに「高さ（または平衡因子：左高さ−右高さ）」を保持し、平衡因子が−1, 0, +1 を超えた場合に右回転/左回転（単回転・二重回転）で再平衡を行います。検索・挿入・削除は最悪ケースでも O(log n)。回転の頻度は赤黒木より多くなる傾向があり、読み出しが多い状況で高さがより低く保たれる利点があります。
赤黒木（Red‑Black Tree）
Rudolf Bayer による「対称二分B木」を源流とし、Guibas & Sedgewick によって赤黒木として整理。各ノードは赤・黒の色ビットを持ち、以下の条件を満たします：ルートは黒、赤ノードの子は黒、任意の葉（NIL）までの黒色ノード数は同じ等。これにより木の高さが 2·log(n+1) を上回らないことが示され、操作は最悪 O(log n)。多くの標準ライブラリ（Java TreeMap、C++実装の多く）が採用しています。
B木 / B+木
ディスクや外部記憶に適した多分岐の平衡木。1ノードが複数鍵を持ち、木の高さを極端に低くできます。データベースやファイルシステムで広く採用。検索・挿入・削除はディスクブロックアクセス回数で評価され、O(log n) に相当しますが「ログ基底」が大きくなるため実用上は非常に浅い木になる点が利点です。
スプレー木（Splay Tree）
Sleator と Tarjan による自己調整木。検索や挿入・削除などの操作後に対象ノードを回転で根に近づける（splay）ことでアクセス局所性を利用します。単一操作は最悪 O(n) になり得ますが、一連の操作に対しての振る舞い（アモルタイズ解析）では平均 O(log n) が保証されます。LRUやキャッシュ用途で有効な場面があります。
トレップ（Treap）
二分探索木の順序鍵に対し、各ノードにランダムな優先度を割り当てヒープ条件も満たすように構成（BST + heap = treap）。ランダム化により期待 O(log n) の高さを実現します。実装が比較的簡単でランダム化により平均性能が良好ですが、確率的保証である点に注意。
再平衡の基本操作 — 左回転／右回転
多くの平衡木が用いる基本操作は「回転」です。左回転（left rotate）はあるノード x の右子 y を昇格させ x を y の左子にする操作、右回転はその逆です。これにより部分木の高さを局所的に調整でき、複数の回転を組み合わせて木全体の平衡を回復します。回転は O(1) の局所操作で、木の順序性（inorder順）を破壊しません。
計算量のまとめ
- 検索：O(log n)（平衡木種類によって「最悪」あるいは「期待/アモルタイズ」での保証）
- 挿入：O(log n)
- 削除：O(log n)
- メモリオーバーヘッド：各ノードが持つ追加情報次第（AVLは2ビット程度、赤黒は1ビット、treapは優先度整数など）
実運用での選択基準
- 読み込みが圧倒的に多い：AVLは赤黒よりも平均的に高さが低く検索が速いケースがあります。
- 挿入/削除が頻繁：赤黒木は再平衡操作が比較的少なく、挿入・削除のオーバーヘッドが抑えられる傾向があるため有利。
- 外部記憶・大規模データ：B木/B+木が必須。ノードあたり多数のキーを持つことでディスクアクセスを最小化。
- アクセス局所性を活かしたい：スプレー木が有効（アムルタイズ保証に基づく）。
- 実装の簡便さ／確率的保証で良い：treap は実装が簡単でランダム化により期待性能が良好。
実装上の注意点と最適化
- 回転実装や親ポインタの更新を漏れなく行う。バグの温床になりやすい。
- メモリ配置：ノードを頻繁に新規割当て/解放する場合はプーリングを使い局所性を高めると高速化できる。
- カラーや平衡因子などの付加情報は最小化する（色は1ビット、平衡因子は2ビット等）ことでメモリとキャッシュ効率が改善。
- スレッド環境：並列化は困難。ロック分割やロックフリー実装、読み込み優先のRCUパターンなどがあるが設計が難しい。
- 永続データ構造（イミュータブル木）：関数型言語での共有可能な更新は部分コピーで実現可能（Okasaki の技法など）。
よくある誤解と落とし穴
- 「赤黒木はAVLより常に遅い」：実測はケース依存。赤黒木は再平衡が緩やかで挿入/削除コストが小さいことが多い。
- 「スプレー木は常に遅い」：単一操作は遅くなり得るが、アクセスパターンに局所性がある場合は高速化する。
- 「B木とB+木は同じ」：B+木は全データを葉に保持し葉が連結されるためレンジ検索に優れる。用途に応じて選択する。
代表的な用途
- 標準ライブラリの連想配列や集合（多くは赤黒木ベース）
- データベースのインデックス（B木 / B+木）
- ファイルシステムのメタデータ管理（B木系）
- 一時キャッシュやアクセス局所性を活かした構造（スプレー木）
まとめ
平衡木は「木が偏ることによる最悪性能」を避け、安定した対数時間アルゴリズムを実現する重要なデータ構造群です。AVL、赤黒、B木、スプレー木、トレップといった複数の実装があり、用途・性能要件・実装コストに応じて使い分けます。ディスクアクセスを最小化するB木系、メモリ内での速い検索を狙うAVL/赤黒、局所性を利用するスプレー木、実装の簡便さを求めるトレップなど、それぞれ得手不得手があります。実装時は回転処理やポインタ更新、メモリレイアウト、スレッド対応といった点に注意してください。
参考文献
- AVL tree — Wikipedia
- Red–black tree — Wikipedia
- B-tree — Wikipedia
- Splay tree — Wikipedia
- Treap — Wikipedia
- G. M. Adelson‑Velsky and E. M. Landis, "An algorithm for the organization of information", 1962
- R. Sedgewick, "Left-leaning red-black trees", 2008（赤黒木の実装解説）
- R. E. Bayer and E. M. McCreight, "Organization and maintenance of large ordered indexes", 1972（B-tree）
- D. D. Sleator and R. E. Tarjan, "Self‑adjusting binary search trees", 1985（Splay tree）
- R. Seidel and C. R. Aragon, "Randomized search trees", 1996（Treap）
- std::map — cppreference（多くの実装が赤黒木を採用）
投稿者プロフィール
