Learning Objectives
- 說明節點高度與平衡因子的定義，並用後序的順序算出每個節點的值
- 寫出右旋與左旋，說明旋轉只改三條連結、中序順序不變，以及為什麼要先更新下面那個節點的高度
- 分辨 LL、RR、LR、RL 四種失衡，說出各自要做單旋轉還是雙旋轉
- 追蹤 AVL 插入：遞迴回程沿路更新高度，在最低的失衡節點旋轉一次就恢復平衡
- 用「高度 h 至少要幾個節點」說明 AVL 樹高是 O(log n)
讓二元搜尋樹自己保持矮
上一課看到，二元搜尋樹的所有操作都是 O(h)，可是依序插入會讓樹高 h 變成 n。我們沒辦法要求資料用「好的順序」進來， 只能讓樹在每次插入、刪除之後自己調整形狀。
AVL 樹是最早提出的自我平衡二元搜尋樹，名稱取自兩位蘇聯數學家 Adelson-Velsky 與 Landis 的姓氏，他們在 1962 年發表這個方法。規則是：
每個節點的左子樹高度與右子樹高度，最多相差 1。
為了隨時檢查這個規則，每個節點多存一個欄位 height：
| 名稱 | 定義 |
|---|---|
高度 height |
空樹是 0；葉節點是 1；其他節點是「左右子樹比較高的那個 + 1」 |
| 平衡因子（balance factor） | 左子樹高度 − 右子樹高度 |
| AVL 的要求 | 每個節點的平衡因子都是 -1、0 或 +1 |
（有些教科書把葉節點的高度算成 0、空樹算成 -1，平衡因子的值不受影響。）
這一課的節點三種語言都是 val、left、right、height 四個欄位，動畫裡每個節點下方的小字就是它的 height。
算出每個節點的高度與平衡因子
先用普通的插入建一棵樹，插入時沒有人更新高度，所以一開始每個節點下方都還是 1。接著 update 用後序走訪由下往上算：一個節點要等兩個子樹都算完，才能算自己。最後根 30 的平衡因子是 2（左邊高 3、右邊高 1），違反 AVL 的要求。
旋轉：只改三條連結
右旋（right rotation）把節點 y 的左子節點 x 轉上來當這棵子樹的新根，y 降成 x 的右子節點：
y x
/ \ / \
x C 右旋 A y
/ \ ───> / \
A B B C
A、B、C 是三棵子樹（可能是空的）。只有 B 換了父節點：它原本在 x 的右邊，現在在 y 的左邊。這樣仍然左小右大，因為 B 裡的值都比 x 大、比 y 小。
從中序來看，旋轉前後都是 A、x、B、y、C，順序完全沒變。
程式只改三條連結，再更新兩個節點的高度：
x = y.left
y.left = x.right # B 換到 y 的左邊
x.right = y # y 降到 x 的右邊
update(y) # y 現在在下面，先更新
update(x) # x 的高度要用到 y 的新高度
return x # 新的子樹根，交給上一層接回去
左旋是鏡像：把右子節點轉上來。旋轉是 O(1)，不管子樹多大都只改這幾個欄位。
LL：左子節點的左邊太高，右旋一次
這次的插入會沿路更新高度，但還不做平衡；建樹約 200 步，可以把進度條拖到印出「旋轉前」的地方。插完 10 之後根 50 的平衡因子是 2，而且多出來的高度在左子節點的左邊，這種形狀叫 LL。在 50 右旋一次：30 轉上來，30 原本的右子樹 40 改掛到 50 的左邊。注意 x.right = y 執行完、y.left = t2 還沒執行的那一步，40 暫時沒有人指著，所以要先用 t2 存起來。
四種失衡與對應的旋轉
插入一個鍵後，從新節點往根的方向，第一個平衡因子變成 +2 或 -2 的節點叫 z。看 z 比較高的那一邊、再往下一層的形狀，分成四種：
| 名稱 | z 的平衡因子 | 高的子節點的平衡因子 | 新鍵在哪裡 | 修法 |
|---|---|---|---|---|
| LL | +2 | +1（左邊高） | z 的左子節點的左邊 | 在 z 右旋 |
| RR | -2 | -1（右邊高） | z 的右子節點的右邊 | 在 z 左旋 |
| LR | +2 | -1（右邊高） | z 的左子節點的右邊 | 先在 z 的左子節點左旋，再在 z 右旋 |
| RL | -2 | +1（左邊高） | z 的右子節點的左邊 | 先在 z 的右子節點右旋，再在 z 左旋 |
LL、RR 叫單旋轉，LR、RL 叫雙旋轉。記法：名稱的兩個字母是「從 z 往下走到新鍵，先走哪邊、再走哪邊」。
為什麼 LR 不能只右旋一次？LR 的新鍵在中間那段子樹（上一張圖的 B），右旋時 B 會整段換到 y 底下，高度原封不動地從左邊搬到右邊，樹還是一樣歪。
先在左子節點左旋，把「內側」的形狀轉成「外側」的 LL，再右旋就正了。
LR：先左旋再右旋
建樹約 200 步，可以把進度條拖到後面。插完 40 之後，根 50 的平衡因子是 +2，但它的左子節點 20 的平衡因子是 -1：新鍵在 20 的右邊，屬於 LR。第一次旋轉在 20 左旋，30 轉上來，形狀變成 50、30、20 一路往左的 LL；第二次在 50 右旋，30 成為新的根。最後 30 的左邊是 20、10，右邊是 50、40、60，平衡因子 0。
想一想：平衡因子與旋轉
用普通的插入依序放進 40、20、60、10、30、25（不做平衡）。根 40 的平衡因子是多少？這是哪一種失衡？
旋轉的程式裡，為什麼右旋要先 update(y) 再 update(x)？
空的 AVL 樹依序插入 3、2、1，最後的根是哪一個？
把旋轉放進插入
完整的 AVL 插入只比普通的遞迴插入多幾行，全部放在遞迴回來的路上：
- 照二元搜尋樹的規則往下，找到空位放新節點
- 回程經過每個祖先時：更新高度、算平衡因子
- 平衡因子是 +2 或 -2，就依上一段的表格做單旋轉或雙旋轉，把旋轉後的新根回傳給上一層
判斷 LL 還是 LR，程式不必記得新鍵走了哪條路，只要比較高的子節點兩邊誰高：h(node.left.left) < h(node.left.right) 表示新鍵在內側，是 LR。
有一個好用的性質：插入之後只要在最低的失衡節點旋轉一次（單旋轉或雙旋轉），這棵子樹的高度就回到插入前的樣子，上面的祖先平衡因子也跟著恢復，不需要再轉。 所以一次插入最多 2 次旋轉，加上往下找位置的 O(log n)，總共 O(log n)。
AVL 插入：依序插入也不會退化
依序插入 10、20、30、40、35。插入 30 時，10 的平衡因子是 -2，屬於 RR，在 10 左旋，20 成為根。插入 35 時，30 的平衡因子是 -2，但它的右子節點 40 的平衡因子是 +1（35 在 40 的左邊），屬於 RL，做兩次旋轉，35 轉到中間。root 要等最外層的 insert 回傳才會換人，所以旋轉發生在根的時候，畫面會在下一步才看到新的根。
為什麼 AVL 樹的高度是 O(log n)
換個方向問：高度是 h 的 AVL 樹，最少要有幾個節點？把這個數記成 N(h)。
最省節點的作法是讓根的一邊高度 h − 1、另一邊高度 h − 2（再矮就違反規則），兩邊也都用最省的方式長：
N(1) = 1
N(2) = 2
N(h) = N(h − 1) + N(h − 2) + 1
| h | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| N(h) | 1 | 2 | 4 | 7 | 12 | 20 | 33 | 54 |
這個遞迴式和費氏數列幾乎一樣，N(h) 會隨 h 指數成長。反過來說，n 個節點的 AVL 樹高度只能是 O(log n)，大約不超過 1.44 log₂n，比完美平衡的 log₂n 多不到一半。 所以搜尋、插入都保證 O(log n)，不再受插入順序影響。
刪除也是一樣的想法：照上一課的方法刪掉節點後，沿著回程更新高度、遇到失衡就旋轉。不同的是，刪除後的旋轉可能讓子樹變矮，失衡會繼續往上傳，最多要旋轉 O(log n) 次。
AVL 的平衡條件很嚴格，樹比較矮、搜尋比較快，代價是插入、刪除時常常要旋轉。下一課的紅黑樹把條件放寬一些，換得更少的調整，C++ 的 std::map 與 Java 的 TreeMap 選的是紅黑樹。
想一想：AVL 的保證
高度是 4 的 AVL 樹，最少有幾個節點？
把 1～7 依序插入一棵空的 AVL 樹，最後印出的根與樹高是什麼？
AVL 樹插入一個鍵之後，最多需要幾次旋轉？
實作：右旋
程式已經有左旋 rotate_left（C++／Java 叫 rotateLeft）和完整的 AVL 插入。請照著左旋的樣子，完成右旋 rotate_right（rotateRight）。測試會插入 50、40、30、20、10、25，經過兩次 LL 和一次 LR，每次都印出前序走訪和各節點的高度。
重點整理
- AVL 樹：每個節點的左右子樹高度最多差 1；每個節點存
height，平衡因子＝左高 − 右高，只能是 -1、0、+1 - 旋轉只改三條連結，中序順序不變、左小右大不變，O(1)；旋轉後先更新在下面的節點，再更新新的子樹根
- 四種失衡：LL 右旋、RR 左旋、LR 先左旋子節點再右旋、RL 先右旋子節點再左旋
- 插入：遞迴回程沿路更新高度，在最低的失衡節點旋轉一次（單或雙），整棵樹就恢復平衡
- 高度 h 至少要 N(h) = N(h−1) + N(h−2) + 1 個節點，所以樹高 O(log n)，搜尋、插入、刪除都是 O(log n)
- 刪除也靠旋轉，但可能要一路轉到根
下一課：2-3-4 樹與紅黑樹。換一種想法：讓一個節點可以放好幾個鍵，樹就永遠完美平衡；再把這種節點用紅、黑兩種顏色的二元樹表示出來。