圖解:什麼是AVL樹?(刪除總結篇)

來源：景禹

作者：景禹

上一篇文章討論了平衡二叉樹的插入操作，沒有看的可以去看一下 圖解：什麼是AVL樹？，有助於理解今天要講的平衡二叉樹的刪除操作。

平衡二叉樹的刪除操作與插入操作類似，先執行標準的BST刪除操作（可以參考文章 圖解：什麼是二叉排序樹？ ），然後進行相應的平衡操作。而平衡操作最基本的兩個步驟就是左旋和右旋，如下圖所示：

平衡二叉樹的刪除操作

與平衡二叉樹的插入操作類似，我們以刪除一個結點

從結點 這裡一定注意和平衡二叉樹插入操作區分開來，y不再是從w回溯到z的路徑上z的孩子，x也不再是z的孫子這樣的描述，一定要注意奧！！！ ）。然後對以 x、y、z 可以的位置有四種情況，BST刪除操作之後的平衡操作也就處理以下四種情況：y 是 z 的左孩子，x 是 y 的左孩子 （Left Left ，LL )；y 是 z 的左孩子，x 是 y 的右孩子 （Left Right ，LR )；y 是 z 的右孩子，x 是 y 的右孩子 （Right Right ，RR )；y 是 z 的右孩子，x 是 y 的左孩子 （Right Right ，RL )；

這裡的四種情況與插入操作一樣，但需要注意的是，插入操作僅需要對以 z 為根的子樹進行平衡操作；而平衡二叉樹的刪除操作就不一樣，先對以 z 為根的子樹進行平衡操作，之後可能需要對 z 的祖先結點進行平衡操作，向上回溯直到根結點。

第一種情況：LL

第二種情況：LR

第三種情況：RR

第四種情況：RL

舉例說明示例一：

我們已刪除下圖中的結點 32 為例進行說明。

第一步：由於 32 結點為葉子結點，直接刪除，並保存刪除結點的父節點 17 。

第二步：從節點 17 向上回溯，找到第一個不平衡結點 44 ，並找到不平衡結點的左右孩子中深度最深的結點 78 （即 y ）；以及 y 的孩子結點當中深度最深的結點 50 （即 x ）。 發現為 RL 的情況。

第三步：對結點 78 進行右旋操作

第四步：對結點 44 進行左旋操作

示例二

我們以刪除下圖中的結點 80 為例進行說明。

第一步，由於結點 80 為葉子結點，則直接刪除，並保存結點 80 的父結點 78 。

第二步：從結點 78 開始尋找第一個不平衡結點，發現就是結點 78 本身（即結點 z ），找到結點 78 深度最深的葉子結點 60 （即結點 y ），以及結點 y 的深度最深的葉結點 55 （即結點 x ）。即 LL 的情況。

第三步：右旋結點 78

第四步：從旋轉後的返回的新的根結點 60 向上回溯（這裡就和平衡二叉樹的插入操作有別了奧，平衡二叉樹的插入操作僅對第一個不平衡結點的子樹進行平衡操作，而AVL的刪除需要不斷地回溯，直到根結點平衡為止 ），判斷是否還有不平衡結點，發現整棵樹的根結點 50 為第一個不平衡結點，找到對應的 y 結點 25 和 x 結點 10 。同樣是 LL 的情況。

第五步：對 z 結點 50 進行右旋操作。

平衡二叉樹的優缺點分析
優點

平衡二叉樹的優點不言而喻，相對於二叉排序樹（BST）而言，平衡二叉樹避免了二叉排序樹可能出現的最極端情況（斜樹）問題，其平均查找的時間複雜度為

缺點

很遺憾，平衡二叉樹為了保持平衡，動態進行插入和刪除操作的代價也會增加。因此出現了後來的紅黑樹，過兩天景禹自會抽時間講解。

時間複雜度分析

左旋和右旋操作僅需要改變幾個指針，時間複雜度為

平衡二叉樹的刪除操作實現

關於左旋與右旋操作，以及平衡因子的計算與之前講的文章 圖解：什麼是AVL樹？ 中的實現是一致的，我們直接看AVL刪除操作的實現代碼：

//返回刪除指定結點後的平衡二叉樹的根結點
struct Node* deleteNode(struct Node* root, int key) 
{ 
 // 步驟一: 標準的BST刪除操作

 if (root == NULL) 
  return root; 

 //如果要刪除的結點的key小於root->key
 //則表示該結點位於左子樹當中，遞歸遍歷左子樹
 if ( key < root->key ) 
  root->left = deleteNode(root->left, key); 

 //如果要刪除的結點的key大於root->key
 //則表示該結點位於右子樹當中，遞歸遍歷右子樹
 else if( key > root->key ) 
  root->right = deleteNode(root->right, key); 

 //找到刪除結點，進行刪除操作
 else
 { 
  // 被刪除結點只有一個孩子或者沒有孩子，
  if( (root->left == NULL) || (root->right == NULL) ) 
  { 
   struct Node *temp = root->left ? root->left : 
           root->right; 

   // temp為空，左右孩子均為空
   if (temp == NULL) 
   { 
    temp = root; 
    root = NULL; 
   } 
   else // 僅有一個孩子
    *root = *temp; //拷貝非空孩子

   free(temp); 
  } 
  else
  { 
   // 被刪除結點左右孩子都存在: 獲取該結點的直接後繼結點
   // 該結點右子樹中最小的結點
   struct Node* temp = minValueNode(root->right); 

   // 將直接後繼結點的值拷貝給刪除結點
   root->key = temp->key; 

   // 刪除其直接後繼結點
   root->right = deleteNode(root->right, temp->key); 
  } 
 } 

 // 如果樹中僅包含一個結點直接返回
 if (root == NULL) 
  return root; 

 //第二步: 更新當前結點的深度
 root->height = 1 + max(height(root->left), 
      height(root->right)); 

 // 第三步: 獲取刪除結點的平衡因子
 // 判斷該結點是否平衡
 int balance = getBalance(root); 

 // 如果結點為不平衡結點，分以下四種情況處理

 // LL情況
 if (balance > 1 && getBalance(root->left) >= 0) 
  return rightRotate(root); 

 // LR情況
 if (balance > 1 && getBalance(root->left) < 0) 
 { 
  root->left = leftRotate(root->left); 
  return rightRotate(root); 
 } 

 // RR情況 
 if (balance < -1 && getBalance(root->right) <= 0) 
  return leftRotate(root); 

 // RL情況
 if (balance < -1 && getBalance(root->right) > 0) 
 { 
  root->right = rightRotate(root->right); 
  return leftRotate(root); 
 } 

 return root; 
} 
實戰應用題目描述
給定一個值 x ，返回一顆平衡二叉樹中比 x 大的結點個數
輸入輸出示例
輸入一個值 x  = 10 和下面的一顆平衡二叉樹：
輸出：4
解釋：平衡二叉樹中比結點10大有 11，13，14，16 ，共4個結點。
題目解析對於平衡二叉樹中的每一個結點維護一個 desc 欄位，用於保存每一個結點所包含的子孫結點的個數。比如示例中結點 10 的 desc 的值就等於 4，結點 10 的子孫結點包含 6、11、5、8 四個結點。計算大於給定結點的節點數目就可以通過遍歷平衡二叉樹獲得了，具體包含以下三種情況：x 比當前遍歷的結點的值大，我們則遍歷當前結點的右孩子。x 比當前遍歷的結點的值小，則大於指定結點的數目加上當前結點右孩子的 desc 加上 2 （加 2 是因為當前結點以及當前結點的右孩子都比指定的值 x 要大，當然是當前結點的右孩子存在的情況下）。具體操作是，判斷當前結點的右孩子是否存在，如果存在則給大於 x 的結點數目加上當前結點的右孩子的 desc 並加2，否則 給大於 x 的結點數目加 1 ；然後將當前結點更新為其左孩子。當 x 等於當前結點的值，判斷 x 的右孩子是否存在，如果存在則將大於 x 的結點數目加上 x 的右孩子 desc ,然後再加上右孩子本身（即 1）；否則，右孩子不存在，則直接返回大於 x 的結點數目。
結點的定義中增加 desc 域：
struct Node { 
    int key; 
    struct Node* left, *right; 
    int height; 
    int desc; 
}; 
我們以查找示例網絡中比結點 6 的結點數目為例講解，比結點 6 的結點數目用 count 表示且初始化為 0；
第一步：訪問根結點 13 ，發現結點 6 的值比 13 小，則 count 的值加上 13 的右孩子 15 的 desc=1 ，再加上結點 13 和 15 本身， count = desc + 2 = 3 .
第二步：訪問結點 13 的左孩子 10 ，6 < 10 ，則 count 的值應加上 10 的右孩子 11 的 desc 的值，再加 2，其中結點 11 的 desc 的值為0，故 count = 3 + 2 = 5 .
第三步：訪問結點 10 的左孩子 6 ，發現與給定值相等，且結點 6 的右孩子存在，則 count 應加上結點 6 的右孩子 8 的 desc 以及結點 8 本身，即 count = 5 + 1 = 6 .
其實歸結到最本質，整個過程就是利用了二叉排序樹中，結點的右子樹的值大於結點，左子樹的值小於結點這樣的特性。
那麼該如何計算每一個結點的 desc 域呢？
插入：每當插入一個新的結點，則給新插入結點的所有父結點的 desc 加 1 。當然相應的旋轉操作也需要進行處理，稍後用圖進行說明。刪除操作：當刪除一個結點，則將刪除結點的所有祖先結點的 desc 減 1 。同樣不論左旋還是右旋都需要進行處理。
還是以之前的左旋和右旋圖說明 desc 值的相應變化：
左旋的情況下：
int val = (T2 != NULL) ? T2->desc : -1; 
x->desc = x->desc - (y->desc + 1) + (val + 1); 
y->desc = y->desc - (val + 1) + (x->desc + 1); 
當 x 的 desc 的值將等於其原來的值減去其原來的右孩子結點 y 的 desc ，再加上左旋之後其右孩子 
右旋的情況下：
int val = (T2 != NULL) ? T2->desc : -1; 
y->desc = y->desc - (x->desc + 1) + (val + 1); 
x->desc = x->desc - (val + 1) + (y->desc + 1); 
與左旋類似，當 y 的值變為其之前的 desc j減去 x 的 desc+1 ，再加上 x 的 desc 則變為其原來的 desc 的值減去 val+1 ，然後再加上旋轉後的 y->desc + 1 。
有了上面的基礎，我們可以一起先來看一下這道題目的左旋和右旋操作。
左右旋操作代碼： 本質上與之前講過的平衡二叉樹插入和刪除操作涉及的左旋與右旋一樣，只是增加了上面的 desc 域的處理操作 （需要複習的就再看一遍代碼，不需要的直接跳過）。
struct Node* rightRotate(struct Node* y) 
{ 
 struct Node* x = y->left; 
 struct Node* T2 = x->right; 

 //旋轉操作，對著圖看
 x->right = y; 
 y->left = T2; 

 // 高度更新
 y->height = max(height(y->left), height(y->right)) + 1; 
 x->height = max(height(x->left), height(x->right)) + 1; 

 // 更新desc 
 int val = (T2 != NULL) ? T2->desc : -1; 
 y->desc = y->desc - (x->desc + 1) + (val + 1); 
 x->desc = x->desc - (val + 1) + (y->desc + 1); 

 return x; 
} 


struct Node* leftRotate(struct Node* x) 
{ 
 struct Node* y = x->right; 
 struct Node* T2 = y->left; 

 //左旋 
 y->left = x; 
 x->right = T2; 

 //更新高度
 x->height = max(height(x->left), height(x->right)) + 1; 
 y->height = max(height(y->left), height(y->right)) + 1; 

 //更新 desc 
 int val = (T2 != NULL) ? T2->desc : -1; 
 x->desc = x->desc - (y->desc + 1) + (val + 1); 
 y->desc = y->desc - (val + 1) + (x->desc + 1); 

 return y; 
} 
獲取結點 N 的平衡因子(複習）：
int getBalance(struct Node* N) 
{ 
 if (N == NULL) 
  return 0; 
 return height(N->left) - height(N->right); 
} 
平衡二叉樹結點的插入操作（增加了對desc的處理，其他和之前講的插入操作的實現一致）：
struct Node* insert(struct Node* node, int key) 
{ 
 /* 標準的BST的插入操作 */
 if (node == NULL) 
  return (newNode(key)); 

 if (key < node->key) { 
  node->left = insert(node->left, key); 
  node->desc++; //插入結點的左右祖先結點的desc++
 } 

 else if (key > node->key) { 
  node->right = insert(node->right, key); 
  node->desc++; 
 } 

 else // 二叉排序樹中不允許插入相同的值
  return node; 

 /* 2. 更新祖先結點的高度 */
 node->height = 1 + max(height(node->left), 
      height(node->right)); 

 /* 3. 獲取祖先結點的平衡因子，判斷是否平衡*/
 int balance = getBalance(node); 

 // 結點不平衡，分一下四種情況處理

 // LL
 if (balance > 1 && key < node->left->key) 
  return rightRotate(node); 

 // RR 
 if (balance < -1 && key > node->right->key) 
  return leftRotate(node); 

 // LR
 if (balance > 1 && key > node->left->key) { 
  node->left = leftRotate(node->left); 
  return rightRotate(node); 
 } 

 // RL
 if (balance < -1 && key < node->right->key) { 
  node->right = rightRotate(node->right); 
  return leftRotate(node); 
 } 

 /*返回插入結點之後，樹的根結點*/
 return node; 
} 
至於刪除操作的修改代碼，我就不在這裡放了，需要的可以對上面的平衡二叉樹刪除操作的代碼修改一下即可。我們主要看一下統計大於給定值 x 的結點個數的代碼。
統計大於結點 x 的結點數目
int CountGreater(struct Node* root, int x) 
{ 
 int res = 0; 

 // 查找結點 x， 同時更新 res的值
 while (root != NULL) { 

  //保存當前結點的右孩子的desc
  //不為空則保存root->right-desc
  //否則保存 -1
  int desc = (root->right != NULL) ? 
    root->right->desc : -1; 

  //如果root的值大於x,則說明 x 位於左子樹當中
  //res = res + 當且結點右孩子的desc + 2
  if (root->key > x) { 
   res = res + desc + 1 + 1; 
   root = root->left; 
  } //當root的值小於 x，則說明 x 位於右子樹當中，繼續查找
  else if (root->key < x) {
   root = root->right; 
  }
  else { //當相等時，res = res + x的右孩子的desc + 1.
   res = res + desc + 1; 
   break; 
  } 
 } 
 return res; 
}