木の回転と平衡（AVL／赤黒木）
値を挿入するたびに各ノードのバランス係数を表示し、|BF| ≥ 2 になった部分木を LL/LR/RL/RR の回転で組み替えて木の高さを抑えます。
50
ノード数 n
—
木の高さ h
—
理論下限 ⌈log₂(n+1)⌉
—
直近の回転
—
回転アニメーション
通常ノード（値）
|BF|≥2 の不均衡ノード 回転の軸（ピボット）
各ノード上の小さな数字 = バランス係数 BF
BF = (左部分木の高さ) − (右部分木の高さ)
二分探索木（高さで色付け・回転で組み替え）
二分探索木は、値を挿入する順番が悪いと「片側にだけ伸びた」鎖のような形になり、探索が
そこで各ノードで バランス係数 BF =（左部分木の高さ）−（右部分木の高さ） を見張り、 |BF| ≥ 2 になったら、その部分木を回転（rotation）で組み替えて高さを下げます。
回転には不均衡の向きに応じて LL・LR・RL・RR の4種類があります。AVL 木はこの規則で常に高さ
値を挿入して BF と木の形がどう変わるか、不均衡が起きた瞬間に回転がどう働くかを確かめてみましょう。
O(n) まで遅くなります。そこで各ノードで バランス係数 BF =（左部分木の高さ）−（右部分木の高さ） を見張り、 |BF| ≥ 2 になったら、その部分木を回転（rotation）で組み替えて高さを下げます。
回転には不均衡の向きに応じて LL・LR・RL・RR の4種類があります。AVL 木はこの規則で常に高さ
O(log n) を保ちます（赤黒木も色の制約で同じ回転を使います）。値を挿入して BF と木の形がどう変わるか、不均衡が起きた瞬間に回転がどう働くかを確かめてみましょう。
いま何が起きている？
ここがポイント
- BF =（左の高さ）−（右の高さ） ── 各ノードの傾きを表し、AVL 木では常に
−1, 0, +1のいずれか。 - |BF| ≥ 2 で回転 ── 不均衡の向きで
LL→右回転 / RR→左回転 / LR・RL→二重回転を選ぶ。 - 回転は探索順序を壊さない ── 中順（in-order）走査の結果は回転前後で同じで、BST の性質を保ったまま高さだけ下げる。
- 高さ O(log n) を維持 ── 自動平衡を切ると鎖状になり高さが n に近づくのに対し、平衡を保つと理論下限に近づく。