平衡木の原理（赤黒木・B木・AVL木）

なぜ「平衡」が要るのか

二分探索木（BST）は「左の子は自分より小さい、右の子は大きい」という順序を保つ木です。検索・挿入・削除は、根から葉に向かって比較しながら下りていくので、計算量は木の高さに比例します。理想的にバランスが取れていれば高さは O(log n) ですが、ここに落とし穴があります。

ソート済みデータを順に挿入すると、右の子だけが伸び続け、木は連結リストと同じ一直線になります。このとき高さは n、検索は O(n) に劣化します。つまりBSTの O(log n) は「たまたま形が良ければ」の話で、保証されていません。

1, 2, 3, 4 を順に挿入すると…

1
 \
  2
   \
    3      ← 高さ n、ただの連結リスト
     \
      4

平衡木（self-balancing tree）は、挿入・削除のたびに形を整え、高さを常に O(log n) に抑えることでこの最悪ケースを排除します。整える操作の主役が回転と（B木系の）分割です。木構造の探索が再帰と相性が良いこと、各操作の速さを表す計算量（Big-O）の記法は前提として進めます。

回転 ― 形を変えても順序を壊さない

回転（rotation）は、平衡木の心臓部です。部分木の親子関係を組み替えて高さを調整しつつ、二分探索木の順序（中順序）は保つという、一見矛盾した要求を満たします。

右回転（x を下げ、左の子 y を上げる）

    x                y
   / \              / \
  y   C    ──→     A   x
 / \                  / \
A   B                B   C

中順序は A y B x C のまま不変。順序は壊れない。

ポイントは、移し替えるのは部分木 B だけで、A < y < B < x < C という大小関係が前後で一切変わらないことです。左回転はこの鏡像です。回転は参照（ポインタ）の付け替えだけなので O(1) で完了します。

AVL木 ― 高さ差を厳格に±1へ

AVL木（1962年, Adelson-Velsky と Landis）は、最初に発明された自己平衡BSTです。平衡条件は厳格で、すべてのノードで「左部分木の高さ − 右部分木の高さ」が -1, 0, +1 のいずれか（この値を平衡係数, balance factor と呼ぶ）。

挿入・削除でこの条件が崩れると、崩れた最も低いノードを起点に回転で回復します。崩れ方は4パターンあり、回転の打ち方が決まっています。

平衡係数を更新し、|bf| > 1 になったら回転
function insert(node, key):
    通常のBST挿入
    高さを更新
    bf = height(left) - height(right)
    if bf > 1 and key < node.left.key:  右回転        # LL
    if bf < -1 and key > node.right.key: 左回転        # RR
    if bf > 1 and key > node.left.key:  左回転後に右回転 # LR
    if bf < -1 and key < node.right.key: 右回転後に左回転 # RL

厳格さの代償として、高さは最大でも約 1.44 * log2(n) と非常に低く保たれます。検索が極めて速い反面、平衡条件が厳しいため挿入・削除で回転が頻発しやすいのが特徴です。

赤黒木 ― 色で緩く縛る

赤黒木（red-black tree）は、各ノードに赤か黒の色を持たせ、次の制約で平衡を保ちます。

• 根は黒。
• 赤ノードの子は必ず黒（赤が連続しない）。
• 任意のノードから葉（NIL）までの経路上の黒ノード数が等しい（黒高さ一定）。

この制約から、最長経路でも最短経路の2倍を超えないことが導けます。よって高さは最大 2 * log2(n+1) 程度に収まり、O(log n) が保証されます。AVLより緩い分木はやや高くなりうるものの、平衡回復に必要な操作が少なくて済みます。

赤黒木の挿入では、まず通常のBST挿入をして新ノードを赤で置き、赤が連続したら「叔父ノードの色」で場合分けして色の塗り替えまたは回転で修復します。重要なのは、色の塗り替えで済むケースが多く、回転は1回の挿入で高々2回に抑えられる点です。削除も同様に回転回数が定数で抑えられます。

B木・B+木 ― ディスクのための多分木

AVLや赤黒木はメモリ内を前提とした二分木です。しかしデータがメモリに乗り切らずディスクやSSDに置かれる場合、設計の前提が変わります。ディスクI/Oは1回が極端に遅く（メモリアクセスの数万倍）、読み取り回数＝木の高さがそのまま性能を決めます。

B木（1970年, Bayer と McCreight）は、1ノードに**多数のキーと子（数百本）**を詰め込む多分木です。1ノードをディスクの1ブロック（ページ）と同じサイズにすると、1回のI/Oで一気に数百方向へ枝分かれできます。子の本数（分岐数, fan-out）が大きいほど木は低くなり、n 件でも高さは log_fanout(n) ＝ わずか3〜4段で済みます。

平衡の保ち方は回転ではなく分割と併合です。

挿入でノードが満杯（キー数 = 2t-1 個）になったら…

[ 10 | 20 | 30 | 40 | 50 ]   ← 満杯ノード
              │ 分割（split）
        [ 30 ]               ← 中央キーを親へ押し上げ
        /     \
[10|20]       [40|50]        ← 左右に分かれる

これにより全ての葉が常に同じ深さに揃う（完全平衡）。

満杯ノードへの挿入は中央のキーを親に押し上げて2つに割る。逆に削除でノードのキーが下限（t-1 個）を割ると、隣から借りる（再分配）か併合する。これらが根に伝播することで、全ての葉が常に同一の深さに保たれます。

B+木 ― 範囲検索に最適化

実際のデータベースやファイルシステムで主流なのは、B木を改良したB+木です。違いは2点。

• データ（値）は葉だけに置く。内部ノードはキー（道しるべ）のみ。これにより内部ノードに多くのキーを詰められ、fan-out がさらに上がる。
• 葉どうしを連結リストでつなぐ。これにより「ある値からある値まで」の範囲検索が、葉を横に走査するだけで高速にできる。

系統と用途の整理

二分探索木から各構造への分岐を、登場年代とともに文章で整理します。

• 1962 二分探索木の最悪ケースを解く最初の解 → AVL木（高さ差±1で厳格・検索特化）。
• 1978 AVLの回転コストを緩める色ベースの平衡 → 赤黒木（Guibas と Sedgewick。1972年のBayerの対称二分B木が原型。更新が軽く汎用、標準ライブラリの定番）。
• 1970 ディスクI/O回数の最小化という別軸の要求 → B木（多分木で木を低く）。
• B木の改良系 範囲検索とfan-out最大化 → B+木（データは葉のみ・葉を連結。DB/FSの主流）。

つまり分岐の根本は「どこにデータがあるか」です。メモリ内なら比較1回が安いので二分木（AVL/赤黒木）で深さを稼いでよく、ディスク/SSDならI/O1回が高いので多分木（B/B+木）で深さを徹底的に削る、という住み分けになります。

まとめ

平衡木の核心は「高さを O(log n) に抑え続ける」一点に尽きます。二分木（AVL・赤黒木）は回転で、多分木（B・B+木）は分割・併合で平衡を保ちますが、選択の決め手は性能特性ではなくデータの置き場所です。比較が安いメモリ内では二分木、I/Oが高いディスク/SSDでは多分木。検索が極端に多いなら厳格なAVL、更新も多い汎用用途なら赤黒木、永続化と範囲検索ならB+木。この対応関係を押さえれば、各構造が「なぜその場面で選ばれるか」を原理から説明できます。なお、これらはデータ構造の中でも順序付き集合・マップを支える基盤であり、std::map や TreeMap の裏側そのものです。