AVL 木

AVL 木は二分探索木の各ノードに高さを保存します。局所の平衡係数が +2 または -2 になると回転して修復し、検索と挿入を O(log n) に保ちます。10..70 の七つの十刻みのキーを順に入れると、辺で数えた高さは AVL が 2、通常の BST が 6。最長検索経路は七ノードから三ノードへ減ります。

回転は近くの二、三ノードの親子関係を変え、木全体を作り直しません。中間キーを局所の根へ上げ、中間順のキー列を保ちます。

AVL 木の仕組み

左が小さく右が大きいという BST の規則に、高さを追加します。

height(node) = 1 + max(height(node.left), height(node.right))

辺数で数えるため null は -1、葉は 0。平衡係数は次です。

BF(node) = height(node.left) - height(node.right)

-1、0、+1 なら有効です。葉を挿入した後、再帰から祖先へ戻り、高さを更新してから BF を計算します。+2 は左が高すぎ、-2 は右が高すぎる状態です。

戻り道で最初の不均衡な祖先を修復します。一つの修復位置に単回転か二重回転を使います。修復後の部分木は挿入前の高さに戻り、それより上で回転は不要です。「修復位置が最大一つ」であり、「回転が最大一回」ではありません。

四種類の回転

最初の文字は重い側、二文字目はその子から見た新キーの方向です。

LR と RL は内側の折れを外向きの直線へ変え、その後で中間キーを局所の根にします。

回転では中間部分木 T2 も移します。左回転で右の子を昇格する場合、その子の旧左部分木を、降格ノードの右へ移します。キーが二つの回転キーの間にあるためです。参照を変え、降格ノードの高さ、昇格ノードの高さの順に更新します。

対象は挿入と検索です。削除は部分木を縮め、複数祖先の修復が必要になる場合があるので、挿入の一箇所修復をそのまま使えません。

操作をステップで追う

既定は insert 30, insert 20, insert 10, insert 25, insert 28, insert 29, search 29 です。

1. 30 を挿入：空の根に高さ 0 の葉を作る。比較用 BST も同じ根。
2. 20 を挿入：30 の左へ。30 は高さ 1、BF(30) = 0 - (-1) = +1。修復なし。
3. 10 を挿入：30、20、左の空きへ進む。戻ると 20 は高さ 1、BF +1、30 は高さ 2、BF +2。LL なので右回転し、20 を根、10 と 30 を子にする。
4. 25 を挿入：20 から右の 30、次に左。30 は左に一段、20 は右に一段重いが両方有効。
5. 28 を挿入：20 -> 30 -> 25 -> right。30 は BF +2、左の子 25 は右へ重く LR。左回転で 28 を 25 の上へ、右回転で 30 の上へ。局所根 28、子 25 と 30。
6. 29 を挿入：20 -> 28 -> 30 -> left。根 20 は BF -2、新キーは右の子 28 の右側なので RR。左回転で 28 を上げる。25 を根とする T2 は 28.left から 20.right へ移り、20 と 28 の間に残る。AVL の辺高さは 2、同順の通常 BST は 4。
7. 29 を検索：AVL は 28 -> 30 -> 29 の三探査、BST は 30 -> 20 -> 25 -> 28 -> 29 の五探査。同じキー集合でも形で経路長が変わる。

祖先を一つずつ戻り、高さ更新、BF 計算、形の分類、最下部の不均衡の修復を行います。小さい木は経路横に高さを出し、密な木は作業台に算式を置きます。

時間・空間計算量

高さの界は最小ノード数から導けます。辺高さ h に必要な最少数を N(h) とすると、最も疎な合法形の子は高さ h - 1 と h - 2 です。

N(-1) = 0, N(0) = 1, N(h) = 1 + N(h - 1) + N(h - 2)

よって N(h) = F(h + 3) - 1。フィボナッチ数は指数的に増えるため、高さは対数です。目安の上界は h <= 1.44 log2(n + 2)。検索は一本の経路、挿入は往復と一回の定数規模の修復です。回転回数が別の対数因子を加えるわけではありません。

AVL を選ぶ時

検索が多く、厳しい高さの界を求めるなら候補になります。書き込み後の高さ管理は必要です。赤黒木はより緩い形を許し、更新の多い順序付き構造で使われます。通常の BST は単純ですが挿入順に依存し、整列済みや意図的な入力で線形検索へ退化します。

境界ケース

• 空：検索は零ノード探査。初挿入は高さ 0 の根。
• 重複：既存ノードで止まり、ノード数、両方の形、保存高さは不変。
• 内側が重い：LR と RL は二重回転が必要。外側の回転だけでは不均衡が残る。
• 空の T2：回転は有効で、移す非空部分木がないだけ。
• 表示上限：15 ノードは画面の制約で、AVL の固定容量ではない。

よくある間違い

• BF の符号を逆にする。 左高さから右高さを引きます。逆の規約なら全判定も逆にします。
• 高さの規約を混ぜる。 null は -1、葉は 0。葉だけ 1 に変えてはいけません。
• 接続変更前に高さを更新する。 旧子からは旧高さしか出ません。変更後、降格、昇格の順です。
• T2 を失う。 二キーの間へ移します。失えばデータ欠落、反対側なら BST 順序違反です。
• 左重をすべて LL とする。 子が内側へ傾くことがあります。二方向目を確認します。
• 挿入後に全祖先を回転する。 最下の不均衡を直せば、合法な上位祖先の回転は不要です。