Interactive
AVL木可視化
AVL木は最初に発明された自己平衡二分探索木で、 すべてのノードで「左部分木の高さ − 右部分木の高さ」（平衡係数）が-1・0・+1のいずれかという厳格な条件を保ちます。 キーを挿入すると、BST探索→葉として追加→根に向かって祖先の高さと平衡係数を再チェックし、 崩れていればLL・RR・LR・RLの4パターンいずれかの回転で直す様子をステップ再生できます。
3 / 20 ノード
このステップで注目h=部分木の高さ bf=平衡係数（左の高さ−右の高さ）
全ノードの平衡係数が-1〜+1に収まり、heightも正しく整合しています（最大|bf|=0）
1 / 1
完了
初期状態（20 → 10 → 30 の順に挿入済み）
ここから好きなキーを挿入して、高さの再計算と回転の過程を観察できます。
ここが分かる
- 崩れ方は4パターンだけ——LL（左の子の左側が重い）は右回転1回、RR（右の子の右側）は左回転1回、LR・RLは「く」の字を一直線に変形してから2回目の回転。どのケースも子（または孫）の平衡係数を見れば一意に決まる。
- 挿入の場合、最初に見つかった不均衡な祖先を1回（単一or二重）回転させるだけで木全体の平衡が戻る——回転後のその部分木の高さは挿入前とまったく同じに戻るため、それより上の祖先は一切変化しない。赤黒木のケース1（再彩色）が祖先を何段も連鎖することがあるのとは対照的。
- 厳格な平衡条件の代償として、AVL木の高さは最大でも約
1.44 log₂nと非常に低く保たれる（赤黒木は約2 log₂n）——検索は速いが、挿入・削除での回転が起きやすい。読み取り中心の辞書に向く。