二叉搜索樹 & 平衡樹

定義

二叉搜索樹是一種二叉樹的樹形數據結構，其定義如下：

1. 空樹是二叉搜索樹。

2. 若二叉搜索樹的左子樹不為空，則其左子樹上所有點的附加權值均小於其根節點的值。

3. 若二叉搜索樹的右子樹不為空，則其右子樹上所有點的附加權值均大於其根節點的值。

4. 二叉搜索樹的左右子樹均為二叉搜索樹。

二叉搜索樹上的基本操作所花費的時間與這棵樹的高度成正比。對於一個有 \(n\) 個結點的二叉搜索樹中，這些操作的最優時間複雜度為 \(O(\log n)\)，最壞為 \(O(n)\)。隨機構造這樣一棵二叉搜索樹的期望高度為 \(O(\log n)\)。

過程

二叉搜索樹節點的定義

實現

struct TreeNode {
  int key;
  TreeNode* left;
  TreeNode* right;
  // 維護其他信息，如高度，節點數量等
  int size;   // 當前節點為根的子樹大小
  int count;  // 當前節點的重複數量

  TreeNode(int value)
      : key(value), size(1), count(1), left(nullptr), right(nullptr) {}
};

遍歷二叉搜索樹

由二叉搜索樹的遞歸定義可得，二叉搜索樹的中序遍歷權值的序列為非降的序列。時間複雜度為 \(O(n)\)。

遍歷一棵二叉搜索樹的代碼如下：

實現

void inorderTraversal(TreeNode* root) {
  if (root == nullptr) {
    return;
  }
  inorderTraversal(root->left);
  std::cout << root->key << " ";
  inorderTraversal(root->right);
}

查找最小/最大值

由二叉搜索樹的性質可得，二叉搜索樹上的最小值為二叉搜索樹左鏈的頂點，最大值為二叉搜索樹右鏈的頂點。時間複雜度為 \(O(h)\)。

實現

int findMin(TreeNode* root) {
  if (root == nullptr) {
    return -1;
  }
  while (root->left != nullptr) {
    root = root->left;
  }
  return root->key;
}

int findMax(TreeNode* root) {
  if (root == nullptr) {
    return -1;
  }
  while (root->right != nullptr) {
    root = root->right;
  }
  return root->key;
}

搜索元素

在以 root 為根節點的二叉搜索樹中搜索一個值為 value 的節點。

分類討論如下：

• 若 root 為空，返回 false。
• 若 root 的權值等於 value，返回 true。
• 若 root 的權值大於 value，在 root 的左子樹中繼續搜索。
• 若 root 的權值小於 value，在 root 的右子樹中繼續搜索。

時間複雜度為 \(O(h)\)。

實現

bool search(TreeNode* root, int target) {
  if (root == nullptr) {
    return false;
  }
  if (root->key == target) {
    return true;
  } else if (target < root->key) {
    return search(root->left, target);
  } else {
    return search(root->right, target);
  }
}

插入，刪除，修改都需要先在二叉搜索樹中進行搜索。

插入一個元素

在以 root 為根節點的二叉搜索樹中插入一個值為 value 的節點。

分類討論如下：

• 若 root 為空，直接返回一個值為 value 的新節點。

• 若 root 的權值等於 value，該節點的附加域該值出現的次數自增 \(1\)。

• 若 root 的權值大於 value，在 root 的左子樹中插入權值為 value 的節點。

• 若 root 的權值小於 value，在 root 的右子樹中插入權值為 value 的節點。

時間複雜度為 \(O(h)\)。

實現

TreeNode* insert(TreeNode* root, int value) {
  if (root == nullptr) {
    return new TreeNode(value);
  }
  if (value < root->key) {
    root->left = insert(root->left, value);
  } else if (value > root->key) {
    root->right = insert(root->right, value);
  } else {
    root->count++;  // 節點值相等，增加重複數量
  }
  root->size = root->count + (root->left ? root->left->size : 0) +
               (root->right ? root->right->size : 0);  // 更新節點的子樹大小
  return root;
}

刪除一個元素

在以 root 為根節點的二叉搜索樹中刪除一個值為 value 的節點。

先在二叉搜索樹中搜索權值為 value 的節點，分類討論如下：

• 若該節點的附加 count 大於 \(1\)，只需要減少 count。

• 若該節點的附加 count 為 \(1\)：

  • 若 root 為葉子節點，直接刪除該節點即可。

  • 若 root 為鏈節點，即只有一個兒子的節點，返回這個兒子。

  • 若 count 有兩個非空子節點，一般是用它左子樹的最大值（左子樹最右的節點）或右子樹的最小值（右子樹最左的節點）代替它，然後將它刪除。

時間複雜度 \(O(h)\)。

實現

方法使用 root = remove(root, 1) 表示刪除根節點為 root 樹中值為 1 的節點，並返回新的根節點。

// 此處返回值為刪除 value 後的新 root
TreeNode* remove(TreeNode* root, int value) {
  if (root == nullptr) {
    return root;
  }
  if (value < root->key) {
    root->left = remove(root->left, value);
  } else if (value > root->key) {
    root->right = remove(root->right, value);
  } else {
    if (root->count > 1) {
      root->count--;  // 節點重複數量大於1，減少重複數量
    } else {
      if (root->left == nullptr) {
        TreeNode* temp = root->right;
        delete root;
        return temp;
      } else if (root->right == nullptr) {
        TreeNode* temp = root->left;
        delete root;
        return temp;
      } else {
        TreeNode* successor = findMinNode(root->right);
        root->key = successor->key;
        root->count = successor->count;  // 更新重複數量
        root->right = remove(root->right, successor->key);
      }
    }
  }
  return root;
}

// 此處以右子樹的最小值為例
TreeNode* findMinNode(TreeNode* root) {
  while (root->left != nullptr) {
    root = root->left;
  }
  return root;
}

求元素的排名

排名定義為將數組元素升序排序後第一個相同元素之前的數的個數加一。

查找一個元素的排名，首先從根節點跳到這個元素，若向右跳，答案加上左兒子節點個數加當前節點重複的數個數，最後答案加上終點的左兒子子樹大小加一。

時間複雜度 \(O(h)\)。

實現

int queryRank(TreeNode* root, int v) {
  if (root == nullptr) return 0;
  if (root->key == v) return (root->left ? root->left->size : 0) + 1;
  if (root->key > v) return queryRank(root->left, v);
  return queryRank(root->right, v) + (root->left ? root->left->size : 0) +
         root->count;
}

查找排名為 k 的元素

在一棵子樹中，根節點的排名取決於其左子樹的大小。

• 若其左子樹的大小大於等於 \(k\)，則該元素在左子樹中；

• 若其左子樹的大小在區間 \([k-\textit{count},k-1]\)（count 為當前結點的值的出現次數）中，則該元素為子樹的根節點；

• 若其左子樹的大小小於 \(k-\textit{count}\)，則該元素在右子樹中。

時間複雜度 \(O(h)\)。

實現

int querykth(TreeNode* root, int k) {
  if (root == nullptr) return -1;  // 或者根據需求返回其他合適的值
  if (root->left) {
    if (root->left->size >= k) return querykth(root->left, k);
    if (root->left->size + root->count >= k) return root->key;
  } else {
    if (k == 1) return root->key;
  }
  return querykth(root->right,
                  k - (root->left ? root->left->size : 0) - root->count);
}

平衡樹簡介

使用搜索樹的目的之一是縮短插入、刪除、修改和查找（插入、刪除、修改都包括查找操作）節點的時間。

關於查找效率，如果一棵樹的高度為 \(h\)，在最壞的情況，查找一個關鍵字需要對比 \(h\) 次，查找時間複雜度（也為平均查找長度 ASL，Average Search Length）不超過 \(O(h)\)。一棵理想的二叉搜索樹所有操作的時間可以縮短到 \(O(\log n)\)（n 是節點總數）。

然而 \(O(h)\) 的時間複雜度僅為理想情況。在最壞情況下，搜索樹有可能退化為鏈表。想象一棵每個結點只有右孩子的二叉搜索樹，那麼它的性質就和鏈表一樣，所有操作（增刪改查）的時間是 \(O(n)\)。

可以發現操作的複雜度與樹的高度 \(h\) 有關。由此引出了平衡樹，通過一定操作維持樹的高度（平衡性）來降低操作的複雜度。

平衡性的定義

關於一棵搜索樹是否「平衡」，不同的平衡樹中對「平衡」有着不同的定義。比如以 T 為根節點的二叉搜索樹，左子樹和右子樹的高度相差很大，或者左子樹的節點個數遠大於右子樹的節點個數，這棵樹顯然不具有平衡性。

對於二叉搜索樹來説，常見的平衡性的定義是指：以 T 為根節點的樹，每一個結點的左子樹和右子樹高度差最多為 1。

• Splay 樹 中，對於任意節點的訪問操作（搜索、插入還是刪除），都會將被訪問的節點移動到樹的根節點位置。

• AVL 樹 每個節點 N 維護以 N 為根節點的樹的高度信息。AVL 樹對平衡性的定義：如果 T 是一棵 AVL 樹，當且僅當左右子樹也是 AVL 樹，且 \(|height(T->left) - height(T->right)| \leq 1\)。

• Size Balanced Tree 每個節點 N 維護以 N 為根節點的樹中節點個數 size。對平衡性的定義：任意節點的 size 不小於其兄弟節點（Sibling）的所有子節點（Nephew）的 size。

• B 樹 對平衡性的定義：每個節點應該保持在一個預定義的範圍內的關鍵字數量。

此外，對於擁有同樣元素值集合的搜索樹，平衡狀態可能是不唯一的。也就是説，可能兩棵不同的搜索樹，含有的元素值集合相同，並且都是平衡的。

平衡的調整過程

對不滿足平衡條件的搜索樹進行調整操作，可以使不平衡的搜索樹重新具有平衡性。

關於二叉平衡樹，平衡的調整操作分為包括 左旋（Left Rotate 或者 zag） 和 右旋（Right Rotate 或者 zig） 兩種。由於二叉平衡樹在調整時需要保證中序遍歷序列不變。這兩種操作均不改變中序遍歷序列。

在這裏先介紹右旋，右旋也稱為「右單旋轉」或「LL 平衡旋轉」。對於結點 \(A\) 的右旋操作是指：將 \(A\) 的左孩子 \(B\) 向右上旋轉，代替 \(A\) 成為根節點，將 \(A\) 結點向右下旋轉成為 \(B\) 的右子樹的根結點，\(B\) 的原來的右子樹變為 \(A\) 的左子樹。

右旋操作只改變了三組結點關聯，相當於對三組邊進行循環置換一下，因此需要暫存一個結點再進行輪換更新。

對於右旋操作一般的更新順序是：暫存 \(B\) 結點（新的根節點），讓 \(A\) 的左孩子指向 \(B\) 的右子樹 \(T2\)，再讓 \(B\) 的右孩子指針指向 \(A\)，最後讓 \(A\) 的父結點指向暫存的 \(B\)。

完全同理，有對應的左旋操作，也稱為「左單旋轉」或「RR 平衡旋轉」。左旋操作與右旋操作互為鏡像。

下面給出左旋和右旋的代碼。

實現

TreeNode* rotateLeft(TreeNode* root) {
  TreeNode* newRoot = root->right;
  root->right = newRoot->left;
  newRoot->left = root;
  // 更新相關節點的信息
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;  // 返回新的根節點
}

TreeNode* rotateRight(TreeNode* root) {
  TreeNode* newRoot = root->left;
  root->left = newRoot->right;
  newRoot->right = root;
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;
}

對於這段示例代碼，在調用時需要保存 root 的父節點 pre。方法返回指向新的根節點的指針，只需要將 pre 指向新的根節點即可。

四種平衡性破壞的情況

雖然不同的二叉平衡樹的定義有所區別，不同二叉平衡樹區別只在於節點維護的信息不同，以及旋轉調整後節點更新的信息不同。二叉平衡樹平衡性被破壞的情況只有以下四種。進行平衡性調整的操作只包括左旋和右旋。以下先介紹四種情況，再對不同的二叉平衡樹進行對比。

LL 型：T 的左孩子的左子樹過長導致平衡性破壞。

調整方式：右旋節點 T。

RR 型：與 LL 型類似，T 的右孩子的右子樹過長導致平衡性破壞。

調整方式：左旋節點 T。

LR 型：T 的左孩子的右子樹過長導致平衡性破壞。

調整方式：先左旋節點 L，成為 LL 型，再右旋節點 T。

RL 型：與 LR 型類似，T 的右孩子的左子樹過長導致平衡性破壞。

調整方式：先右旋節點 R，成為 RR 型，再左旋節點 T。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：2323122, aofall, AtomAlpaca, Bocity, CoelacanthusHex, countercurrent-time, Early0v0, Enter-tainer, fearlessxjdx, Great-designer, H-J-Granger, hsfzLZH1, iamtwz, Ir1d, ksyx, Marcythm, NachtgeistW, ouuan, Persdre, shuzhouliu, StudyingFather, SukkaW, Tiphereth-A, wsyhb, Yesphet, yuhuoji, lingkerio
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用