平衡木とは（全体像）
平衡木は、木の左右の高さをそろえて、検索の速さを保つ木構造のこと。ふつうの2分探索木を「整えたもの」だと考えるとよい。
2分探索木は、左に小さい値・右に大きい値を置いて、半分ずつしぼって探せるのが利点だ。ところが、たとえば小さい順にデータを入れていくと、右へ右へと一直線に伸びてしまう。こうなると木の利点が消え、先頭からたどるのと同じくO(n)（遅い）になってしまう。
そこで平衡木は、データを入れるたびに形を整えて、左右の高さの差を小さく保つ。これで、どんな入れ方をしても検索はO(log n)（速い）のままになる、というしくみだ。
詳しく：3種類の使い分けだけ覚えれば戦える
ここが記事の心臓部。平衡木の中身は、次の表に全部つまっている。`O(log n)`は「データが増えても、ほんの少しずつしか時間が増えない速さ」だと思えばよい。
平衡木の3種類
| 種類 | 平衡のきびしさ | 得意なこと | おもな使われ方 |
|---|---|---|---|
| AVL木 | きっちり（高さ差≦1） | 検索が速い | 検索を重視する場面 |
| 赤黒木 | ゆるめ | 挿入・削除が速い | プログラム言語の標準ライブラリなど汎用 |
| B木 | 多分岐（枝が多い） | まとめて読み書き | データベースのインデックス・ファイルシステム |
3種類はどれも「検索O(log n)を保証する」点は同じで、平衡のきびしさと得意分野が違う。
- AVL木 … 左右の高さの差を1以下にきっちり保つ。形を細かく整えるぶん検索は速いが、出し入れの手間はやや多い。
- 赤黒木 … 平衡をゆるめにして、出し入れを速くしたタイプ。多くのプログラム言語の標準的なデータ構造で使われている。
- B木 … 1つの節点が枝を3本以上持てる「枝分かれの多い木」。1回でまとめて読み書きできるので、ディスクを使うデータベースやファイルシステムで活躍する。
つまり、「検索重視ならAVL・出し入れ重視なら赤黒木・データベースならB木」という対応で押さえると整理しやすい、というわけだね。
わかりやすく言い換えると
要するに、平衡木は「かたよらないように整えた木」だ。
①AVL木 … きっちり整える優等生（検索が速い）
②赤黒木 … ほどよく整える効率派（出し入れが速い）
③B木 … 枝をたくさん持つまとめ役（データベース向き）
2分探索木をそのまま使うと、かたよって遅くなることがある。それを整えて速さを守るのが平衡木、と覚えるとよい。
試験のツボ
🔴 一番出る：平衡木は検索O(log n)を保証する
①2分探索木はかたよるとO(n)になることがある
②平衡木は高さを整えてO(log n)を保つ
🔴 次に出る：AVL木と赤黒木の違い
①AVL木はきっちり平衡で検索が速い
②赤黒木はゆるい平衡で出し入れが速い
🟡 押さえると安定：B木の用途
①B木は枝分かれが多い（多分岐）
②データベースのインデックスやファイルシステムで使う
よくある間違い
①「2分探索木は平衡木と同じもの」→ ✗ 2分探索木はかたよることがある。高さを整えて速さを保証するのが平衡木。
②「AVL木と赤黒木はまったく同じもの」→ ✗ 平衡のきびしさが違う。AVLはきっちり、赤黒木はゆるめ。
③「B木は枝が必ず2本までの木」→ ✗ B木は枝を3本以上持てる多分岐の木。だから枝が2本までとは限らない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（平衡木の役割）
平衡木の役割に関する次の記述のうち、正しいものはどれか。
- 平衡木はわざとデータをかたよらせ、検索をO(n)に近づけてしまうためのしくみのことだ
- 平衡木は左右の高さを整えて、検索の速さをO(log n)に保つための木構造だ
- 平衡木は2分探索木と同じもので、かたよっても速さは変わらないとされる
- 平衡木はデータの並びを記録せず、要素を検索することはできないものだ
解答は 2 だよ。
平衡木は左右の高さを整えて、検索をO(log n)に保つ木なんだ。2分探索木はかたよるとO(n)になることがあるけど、平衡木はそれを防ぐよ。
選択肢1の「わざと遅くする」、選択肢3の「BSTと同じ」、選択肢4の「検索できない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 速さを保つための木 |
| 2 | ✓ | 高さを整えてO(log n)を保つ |
| 3 | ✗ | BSTはかたよると遅くなる |
| 4 | ✗ | 検索のための木 |
オリジナル問題2（AVL木と赤黒木）
AVL木と赤黒木に関する次の記述のうち、正しいものはどれか。
- AVL木はきっちり平衡で検索が速く、赤黒木はゆるい平衡で出し入れが速い
- AVL木はゆるい平衡で出し入れが速く、赤黒木はきっちり平衡で検索が速い
- AVL木も赤黒木もまったく平衡を取らないので、どちらも検索はO(n)で遅くなる
- AVL木と赤黒木は平衡のきびしさも用途も同じで、両者にはなんの違いもない
解答は 1 だよ。
AVL木はきっちり平衡で検索が速い、赤黒木はゆるい平衡で出し入れが速いんだ。どちらも検索はO(log n)を保つけど、平衡のきびしさが違うよ。
選択肢2はAVLと赤黒木が逆。選択肢3の「平衡を取らない」、選択肢4の「違いがない」も誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | AVL＝検索重視・赤黒木＝出し入れ重視 |
| 2 | ✗ | AVLと赤黒木が逆 |
| 3 | ✗ | どちらも平衡を取る |
| 4 | ✗ | 平衡のきびしさが違う |
オリジナル問題3（B木の用途）
B木に関する次の記述のうち、正しいものはどれか。
- B木は枝が必ず2本までの木で、データベースではいっさい使われないとされている
- B木は平衡を取らない木なので、検索はかならずO(n)になってしまう木だ
- B木は枝を3本以上持てる多分岐の木で、データベースのインデックスで活躍する
- B木は枝分かれを持たない一直線の構造で、ファイルシステムには向かない
解答は 3 だよ。
B木は枝を3本以上持てる多分岐の木で、まとめて読み書きできるからデータベースのインデックスやファイルシステムで活躍するんだ。
選択肢1の「2本まで・DBで使わない」、選択肢2の「O(n)」、選択肢4の「一直線」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 多分岐でDBで使われる |
| 2 | ✗ | 平衡木なのでO(log n) |
| 3 | ✓ | 多分岐でDBインデックス向き |
| 4 | ✗ | 枝分かれの多い木 |
まとめ
押さえどころ
- 🔴 平衡木の役割 ＝ 左右の高さを整えて、検索をO(log n)に保つ。2分探索木のかたより対策。
- 🔴 AVL木と赤黒木 ＝ AVLはきっちり平衡で検索が速い、赤黒木はゆるい平衡で出し入れが速い。
- 🟡 B木 ＝ 枝分かれの多い多分岐の木。データベースのインデックスやファイルシステムで活躍。
次に学ぶ
- 木構造・ヒープ ── 平衡木のもとになる木構造の基本。親子関係や高さの考え方を押さえると平衡木が腑に落ちる。
- 探索アルゴリズム ── 木やデータの中から目的の値を見つける方法。O(log n)の速さの意味がつかめる。
執筆: SikakuQuest編集部