[[423024]]

AVL 樹的意義：是二分查找樹 BST 。二分查找樹查找某個值時，時間復雜度是 O(h) ，因此，我們讓樹的盡可能平衡，即最大高度盡可能的小。因此有了 AVL 。

參考例題：

• AcWing：AVL樹的根[1]

百度百科[2]：在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。AVL樹得名于它的發明者G. M. Adelson-Velsky和E. M. Landis，他們在1962年的論文《An algorithm for the organization of information》中發表了它。

BST 本質上是維護一個有序序列，AVL 樹中的左旋右旋操作，并不會改變樹的中序遍歷結果。

上圖中把 A 右旋是怎么做的呢?把 B 旋轉到根節點，然后把 A 變成 B 的右孩子，把 E 補償給 A 作為 A 的左孩子。

左旋和右旋

對節點 u 右旋：

• 根 u 的左兒子變成新的根 p
• 根的左兒子變成新的根 p 原本的右兒子
• 新的根 p 的右兒子變成了原本的根 u
• u 和 p 的高度都需要更新

void R(int& u) 
{ 
    int p = l[u]; 
    l[u] = r[p], r[p] = u; 
    update(u), update(p); 
    u = p; 
} 

對節點 u 右旋：

• 根 u 的右兒子變成新的根 p
• 根的右兒子變成新的根 p 原本的左兒子
• 新的根 p 的左兒子變成了原本的根 u
• u 和 p 的高度都需要更新

void L(int& u) 
{ 
    int p = r[u]; 
    r[u] = l[p], l[p] = u; 
    update(u), update(p); 
    u = p; 
} 

高度更新由左右兒子決定，因為求高度時，默認其兩個兒子已經更新完高度了：

void update(int u) 
{ 
    h[u] = max(h[l[u]], h[r[u]]) + 1; 
} 

插入的四種情況

四種情況

(一)新數字插到了左子樹，導致左子樹比右子樹高2;左孩子的左子樹比其右子樹高1

對于四種情況中的①。應該右旋 A 。

實例如上圖，右旋 88 即可。

(二)新數字插到了左子樹，導致左子樹比右子樹高2;左孩子的右子樹比其左子樹高1

對于四種情況中的③。應該左旋 B 再右旋 A 。

對應的情況如如下：

  70 
61 
  65 
// 左旋 61 
    70 
  65 
61 
// 右旋 70 
  65 
61  70 

(三)新數字插到了右子樹，導致右子樹比左子樹高2;右孩子的右子樹比其左子樹高1

對于四種情況中的②。應該左旋 A 。

對應的情況如 88 96 120 ，左旋 88 即可。

(四)新數字插到了右子樹，導致右子樹比左子樹高2;右孩子的左子樹比其右子樹高1

對于四種情況中的④。應該右旋 B 再左旋 A 。

對應的情況如如下：

  70 
96 
  88 
// 右旋 96 
70 
  88 
    96 
// 左旋 70 
  96 
70  88 

插入的代碼

void insert(int& u, int w) 
{ 
    if (!u) u = ++ idx, v[u] = w; 
    else if (w < v[u]) 
    { 
        insert(l[u], w); 
        if (get_balance(u) == 2) 
        { 
            if (get_balance(l[u]) == 1) R(u); 
            else L(l[u]), R(u); 
        } 
    } 
    else 
    { 
        insert(r[u], w); 
        if (get_balance(u) == -2) 
        { 
            if (get_balance(r[u]) == -1) L(u); 
            else R(r[u]), L(u); 
        } 
    } 
 
    update(u); 
} 

參考資料

[1]AVL樹的根: https://www.acwing.com/problem/content/description/1554/

[2]百度百科: https://baike.baidu.com/item/AVL%E6%A0%91/10986648