上文鏈接

• 【C++】AVL樹（詳解）

一、什么是紅黑樹

我們之前學習過了二叉搜索樹和 AVL 樹，紅黑樹和 AVL 樹一樣，也是一棵自平衡的二叉搜索樹，AVL 樹是通過控制左右子樹的高度差不超過 1 來保持平衡，而紅黑樹則是為每個結點增加一個存儲位來表示結點的顏色，可以是紅色或者黑色。 通過對任何一條從根到葉子的路徑上各個結點的顏色進行約束來保持樹的左右兩邊的相對平衡。紅黑樹確保沒有一條路徑會比其他路徑長出 2 倍，即 2 * 最短路徑 >= 最長路徑，因而是接近平衡的。

如下圖所示就是一棵紅黑樹：

---

二、紅黑樹的性質

1. 顏色規則

紅黑樹為何能夠確保沒有一條路徑會比其他路徑長出 2 倍呢？是因為它有如下四個規則：

1. 每個結點不是紅色就是黑色；
2. 根結點是黑色的；
3. 如果一個結點是紅色的，則它的兩個孩子結點必須是黑色的，也就是說任意一條路徑不會有連續的紅色結點；
4. 對于任意一個結點，從該結點到其所有空結點的簡單路徑上，均包含相同數量的黑色結點。

說明：《算法導論》等書籍上補充了一條每個葉子結點 (NIL) 都是黑色的規則。他這里所指的葉子結點不是傳統的意義上的葉子結點，而是我們說的空結點，有些書籍上也把 NIL 叫做外部結點。NIL 是為了方便準確的標識出所有路徑，《算法導論》在后續講解實現的細節中也忽略了 NIL 結點，所以我們知道一下這個概念即可。

有了上面的描述，我們可以總結出紅黑樹的性質：

• 左根右：由于它是二叉搜索樹，所以左子樹的值 < 根 < 右子樹的值；
• 根葉黑：根節點和葉子節點 (NIL) 都是黑色的；
• 不紅紅：一條路徑上不會出現兩個連續的紅色節點；
• 黑路同：任意兩條路徑上的黑色節點個數相同。

因此，紅黑樹的性質可以簡記為：左根右，根葉黑，不紅紅，黑路同。

---

2. 紅黑樹的規則為什么可以控制平衡

為什么有了上面四條規則就可以確保紅黑樹中沒有一條路徑會比其他路徑長出 2 倍呢？

由黑路同可知，從根到空結點的每條路徑都有相同數量的黑色結點，所以極端場景下，最短路徑就是全為黑色結點的路徑，假設最短路徑長度為 h。

又由不紅紅可知，任意一條路徑不會有連續的紅色結點，所以極端場景下，最長的路徑就是一黑一紅間隔組成，那么最長路徑的長度就為 2 * h。

綜上所述，在最極端的情況下，紅黑樹中的最長路徑也才剛好是最短路徑的兩倍，所以對于任意一棵紅黑樹來說 2 * 最短路徑 >= 最長路徑，因此沒有一條路徑會比其他路徑長出 2 倍。

---

3. 紅黑樹的效率

紅
黑樹與 AVL 樹的增刪查改的效率都是在同一個檔次，時間復雜度都是 $O(\log N)$。

在插入和刪除方面，由于 AVL 樹的平衡條件相對嚴格一些，因此需要頻繁地進行旋轉操作，效率比紅黑樹略低；

在查找方面，紅黑樹不像 AVL 樹那樣保持嚴格的平衡，因此在查找時的效率會比 AVL 樹略低。

---

三、紅黑樹的整體結構

#pragma once
// 枚舉值表示顏色 
enum Colour
{RED,BLACK
};// 這里我們默認按 key-value 結構實現
template<class K, class V>
struct RBTreeNode
{// 這里更新控制平衡也要加入 parent 指針 pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:// ...private:Node* _root = nullptr;
};

---

四、紅黑樹的插入

1. 空樹的插入

當我們對一棵空的紅黑樹進行插入時，直接插入并把其顏色設置為黑色即可。

（下面所討論的插入操作都是建立在樹非空的情況之上）

---

2. 插入節點的父親為黑色

首先我們需要明確一點，在紅黑樹非空的情況下，我們插入一個節點的顏色必定是紅色。

這是因為如果我們把插入節點的顏色設置為黑色的話，那么此時這棵紅黑樹就必然會違反黑路同的性質，之后想要把每條路上的黑色節點數量調整為一樣多的話就會非常麻煩。所以從這個角度來看，樹非空的情況下我們插入的節點都設置為紅色。

此時如果它的父親是黑色，那么將不會違反紅黑樹的任何一條性質，那么插入結束。

---

3. 插入節點的父親為紅色

(1) 叔叔為紅色：變色

我們插入的節點為紅色，此時如果它的父親也為紅色，那么就會違反不紅紅的性質，那么此時必然我們會讓父親變為黑色，但這也意味著父親這條路上多了一個黑色節點，違反了黑路同，我們需要調節黑色節點的數量。此時我們可以讓父親的父親 (爺爺) 變為紅色 (由于父親為紅，所以爺爺變之前必然為黑)，再讓叔叔節點變為黑色，這樣一來，我們就可以滿足不紅紅和黑路同兩個性質了。

但是，此時由于爺爺變紅，可能又會導致出現兩個紅色節點相鄰的情況，因為爺爺的父親可能為紅色。此時我們只需要把爺爺當作新插入的節點，重復上面的操作即可。下面是圖片演示：

注：下圖中用 c (cur) 表示插入節點，用 p (parent) 表示父節點，用 g (grandparent) 表示爺爺節點，用 u (uncle) 表示叔叔節點。

一直重復這樣的操作，直到不違反紅黑樹的性質或者到根為止。注意到根的時候需要把根變為黑色。

---

(2) 叔叔為空或為黑色：旋轉 + 變色

① LL 型：右單旋 + 變色

父親節點為紅色，叔叔節點為空或為黑色時，我們需要先進行旋轉操作。注意前面我們說過空節點 (NIL) 一定是黑色，所以為空或者為黑色其實是一種情況。具體怎么旋轉呢？

如果此時插入節點的父親節點在爺爺節點的左邊 (left)，插入節點在父親節點的左邊 (left)，那么我們把這種情況成為 LL 型。如果是 LL 型，那么需要將以爺爺節點為根的子樹進行右單旋操作，旋轉之后將爺爺和父親節點進行變色 (紅變黑，黑變紅)。這樣操作之后，將不會違反紅黑樹的性質，插入結束。

這種旋轉 + 變色的操作不僅會出現在單純的插入過程中，也有可能出現在我們上面講的情況 (1) 的過程中。即在情況 (1) 的向上變色更新過程中發現 cur 的叔叔顏色為黑就需要進行旋轉 + 變色。

---

② RR 型：左單旋 + 變色

如果此時插入節點的父親節點在爺爺節點的右邊 (right)，插入節點在父親節點的右邊 (right)，那么我們把這種情況成為 RR 型。如果是 RR 型，那么需要將以爺爺節點為根的子樹進行左單旋操作，旋轉之后將爺爺和父親節點進行變色 (紅變黑，黑變紅)。這樣操作之后，將不會違反紅黑樹的性質，插入結束。

可以看到這種情況與上面的 LL 型幾乎一樣，就是一個對稱的關系，這里就不畫圖演示了。

---

③ LR 型：左右雙旋 + 變色

如果此時插入節點的父親節點在爺爺節點的左邊 (left)，插入節點在父親節點的右邊 (right)，那么我們把這種情況成為 LR 型。如果是 LR 型，那么需要將以爺爺節點為根的子樹進行左右雙旋操作，旋轉之后將 cur 和爺爺節點進行變色，插入結束。

---

④ RL 型：右左雙旋 + 變色

如果此時插入節點的父親節點在爺爺節點的右邊 (right)，插入節點在父親節點的左邊 (left)，那么我們把這種情況成為 RL 型。如果是 RL 型，那么需要將以爺爺節點為根的子樹進行右左雙旋操作，旋轉之后將 cur 和爺爺節點進行變色，插入結束。

這種情況與 LR 型完全對稱。

---

4. 代碼部分

// 旋轉代碼的實現跟 AVL 樹非常類似的，只是不需要更新平衡因子
bool Insert(const pair<K, V>& kv)
{// 如果是空樹那么直接讓插入節點變為黑if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;// 走正常二叉搜索樹的插入邏輯，找到插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);// 新增結點顏色給紅色 cur->_col = RED;if (parent->_kv.first < kv.first) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 如果新增節點的父親為紅色，那么需要進行平衡調整// 直到調整到根或者父親為黑色為止，因為判斷條件有兩個while (parent && parent->_col == RED){Node* grandfather = parent->_parent;// 如果此時父親節點在爺爺節點的左邊if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 如果叔叔節點為紅色，那么進行變色處理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;  // 更新 cur 繼續向上處理parent = cur->_parent;}// 如果叔叔為黑色或者為空，那么需要旋轉 + 變色else{// 如果插入在父親節點的左邊，此時為 LL 型if (cur == parent->_left){// 右單旋 + 變色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// LR 型else{// 左右雙旋 + 變色RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 旋轉 + 變色操作完是一定符合紅黑樹的性質的，因此直接結束更新break;}}// 父親節點在爺爺節點的右邊else{Node* uncle = grandfather->_left;// 叔叔節點為紅色，變色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理 cur = grandfather;parent = cur->_parent;}// 叔叔為黑色或為空else{// RR 型if (cur == parent->_right){// 左單旋 + 變色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// RL 型else{// 右左雙旋 + 變色RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 停止更新break;}}}// 變色更新到根節點時有可能根為紅色，需要將根變為黑色_root->_col = BLACK;return true;
}

---

五、紅黑樹的查找與刪除

紅黑樹的查找與正常二叉搜索樹的查找邏輯一樣。

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key) cur = cur->_right;else if (cur->_kv.first > key) cur = cur->_left;else return cur;}return nullptr;
}

紅黑樹的刪除操作這里不做重點講解，這個操作會比插入稍復雜一些，具體操作可以參考《算法導論》或者《STL源碼剖析》中的講解。

---

六、紅黑樹的平衡驗證

如何判斷一棵紅黑樹是否合格呢？這里獲取最長路徑和最短路徑，檢查最長路徑不超過最短路徑的 2 倍是不可行的，因為就算滿足這個條 件，紅黑樹也可能顏色不滿足規則，當前暫時沒出問題，后續繼續插入還是會出問題的。所以我們還是去檢查 4 點規則，滿足這 4 點規則，一定能保證最長路徑不超過最短路徑的 2 倍。

1. 枚舉顏色類型，保證顏色不是黑色就是紅色；
2. 檢查根的顏色是否為黑色即可；
3. 不紅紅：前序遍歷檢查，
   遇到紅色結點查孩子是否是紅色這樣不太方便，因為孩子有兩個，且不一定存在，但是反過來檢查父親的顏色就方便多了；
4. 黑路同：前序遍歷，遍歷過程中用形參記錄根到當前節點路徑的 blackNum (黑色結點數量)，前序遍歷遇到黑色結點就 ++blackNum，走到空就計算出了一條路徑的黑色結點數量。再用任意一條路徑黑色結點數量作為參考值，依次比較即可。

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){// 前序遍歷走到空時，意味著一條路徑走完了 //cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色結點的數量不相等的路徑" << endl;return false;}return true;}// 檢查孩子不太?便，因為孩子有兩個，且不一定存在，反過來檢查父親就方便多了 if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在連續的紅色結點" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);
}bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED)return false;// 參考值 int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);
}