紅黑樹是一種自平衡二叉查找樹，每個節點都帶有顏色屬性，顏色或為紅色或為黑色，可以理解為 AVL 樹的進階版，建議系統學習完 AVL 樹再來看本篇博客

傳送門：C++漫步結構與平衡的殿堂：AVL樹

1.紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是 Red 或 Black。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保最長路徑的節點數量不超過最短路徑節點數量的兩倍（剛好兩倍是可以的），因而是接近平衡的

一個合格的紅黑樹需要滿足以下條件：

• 每個結點不是紅色就是黑色
• 根節點是黑色的
• 如果一個節點是紅色的，則它的兩個孩子結點必須是黑色的，任何路徑都沒有連續的紅色節點，也就是說可以有連續的黑色節點，但不可能一顆紅黑樹全是黑色節點
• 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色節點
• 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)

為什么滿足上面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？

最短路徑就是僅由黑色節點構成的路徑。因為如果路徑中插入紅色節點，會使路徑變長，而全黑路徑不包含額外紅色節點，所以是最短的

最長路徑是紅黑交替出現的路徑。即每一個黑色節點后面都跟著一個紅色節點（但紅色節點后不能再有紅色節點）

設最短路徑的黑色節點數量為 n ，由于所有路徑黑色節點數量相同，最長路徑的黑色節點數量也為 n ，那么最長路徑由于紅黑交替的節點總數最多為 2n 。所以，最長路徑的節點個數不會超過最短路徑節點個數的兩倍

2.紅黑樹的結構

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

在節點的定義中，為什么要將節點的默認顏色給成紅色的？

紅黑樹的性質要求從根節點到每個葉子節點的路徑上黑色節點數量相同。將新節點設為紅色，在插入過程中，如果其父節點是黑色，那么插入紅色節點不會影響任何路徑上黑色節點的數量，也就不需要對樹進行調整來滿足紅黑樹的性質，從而減少了調整的可能性，提高了插入操作的效率

如果新節點是黑色，那么插入后可能會導致某個路徑上的黑色節點數量增加，這會引發更復雜的 “雙黑” 問題，即刪除或插入操作后出現一個節點需要同時承擔兩個黑色節點的情況，處理起來相對復雜。而默認新節點為紅色，出現的問題主要是紅節點沖突，處理相對簡單，以下的插入會詳細解釋原因

3.紅黑樹的插入

typedef RBTreeNode<K, V> Node;
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;// u存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且為黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

對于插入的節點，可能會遇到三種情況：

🚩uncle存在且為紅

我們定義插入節點為 cur，其父節點為 parent，父節點的兄弟節點為 uncle，父節點的父節點為 grandfather

當新插入節點的雙親節點顏色為紅色時，就違反了不能有連在一起的紅色節點，想要盡可能不破壞紅黑樹的平衡結構的情況下正常插入，那么通過變色解決是最好的

不能連續出現紅色節點，還要保持每條路徑的黑色節點相同，可以將 parent 和 uncle 變黑，grandfather 變紅解決

發現處理完之后，在子樹上是保持平衡的，但是 grandfather 又出現了連續紅色節點，這是其中一種情況，總共有三種情況：

1. grandfather 沒有父親，就是根，直接變黑就好了
2. grandfather 有父親，父親是黑色，直接結束
3. grandfather 有父親，父親是紅色，重復上述操作

很明顯示例就是第三種

🚩uncle不存在

當 uncle 不存在的時候，發現通過變色已經不能解決問題了，這個時候就要旋轉調整結構了，根據 cur 的位置判斷進行單旋還是雙旋

然后根據結構性質進行變色即可

🚩uncle存在且為黑

當 uncle 存在且為黑的時候，情況和 uncle 不存在是一樣的

🔥值得注意的是： AVL 樹旋轉可以根據平衡因子為 2 的相對位置來判斷是要單旋還是雙旋，紅黑樹根據 grandfather，parent，cur 的相對位置來判斷，也就是要多畫圖

4.紅黑樹的刪除

紅黑樹的刪除本節不做講解，有興趣可參考：《算法導論》或者《STL源碼剖析》

傳送門：博客園相關講解

5.紅黑樹與AVL樹的比較

可是紅黑樹的時間復雜度比AVL樹更高啊，為什么反而用的更多？

紅黑樹	AVL樹
最長路徑不超過最短路徑的2倍	高度差不超過1
10億個值	10億個值
2*logN->60	logN->30

可以看到數據，性能處理上大概相差兩倍，但是要知道 CPU 的性能是很強大的，每秒能處理十幾億的數據，這點差距根本不足為懼，而且紅黑樹和 AVL 樹是處于同一量級的，但是 AVL 樹的插入刪除需要大量的旋轉，控制嚴格平衡的代價太大，因此使用紅黑樹更多

6.紅黑樹的驗證

🚩檢查是否有連續紅色節點

bool CheckColour(Node* root, int blacknum, int benchmark)
{if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出現連續紅色節點" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}

🚩檢查是否平衡

bool IsBalance()
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基準值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);
}int Height()
{return Height(_root);
}int Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

---

希望讀者們多多三連支持

小編會繼續更新

你們的鼓勵就是我前進的動力！