AVL 木の回転 — 単回転と二重回転の解説

AVL 木の回転

AVL 木は挿入または削除により左右の部分木の高さの差が 1 を超えた場合に回転を実行してバランスを維持します。4つの回転ケースがあります。

バランスファクター

ノードのバランスファクター：BF(node) = height(left) - height(right)

• BF = -1, 0, 1 — バランスしている（回転不要）
• BF > 1 — 左に重い（右回転または左右回転が必要）
• BF < -1 — 右に重い（左回転または右左回転が必要）

ケース 1：右回転（Left-Left ケース）

ノードが左に重く、その左の子も左に重い場合：

回転前（BF=2）:     右回転後:
      30                  20
     /                   /  \
    20                  10   30
   /
  10

ケース 2：左回転（Right-Right ケース）

右回転のミラー：

回転前（BF=-2）:    左回転後:
  10                    20
    \                  /  \
     20               10   30
      \
       30

ケース 3：左右回転（Left-Right ケース）

ノードが左に重いが左の子が右に重い — 2回の回転が必要：

回転前:          左回転(10)後:        右回転(30)後:
    30                30                    20
   /                 /                     /  \
  10               20                    10   30
    \             /
     20          10

ケース 4：右左回転（Right-Left ケース）

左右のミラーです。

計算量

各回転は O(1) 時間 — 一定数のポインタのみを再配置します。挿入後は最大 1 回の回転（単または二重）が必要です。削除後、回転はルートまで伝播する可能性がありますが、合計では O(log n) です。