各位大佬好，我是落羽！一個堅持不斷學習進步的大學生。
如果您覺得我的文章有所幫助，歡迎多多互三分享交流，一起學習進步！
也歡迎關注我的blog主頁: 落羽的落羽

一、紅黑樹的概念與規則

紅黑樹是一種更加特殊的平衡二叉搜索樹，它在每個節點上增加一個存儲位來表示 節點的顏色（紅色或黑色） ，并通過幾條規則確保樹在插入和刪除操作后仍然保持平衡。

紅黑樹有以下四條規則：

1. 每個結點不是紅色就是黑色
2. 根結點是黑色的
3. 如果一個結點是紅色的，則它的兩個孩子必須都是黑色的，也就是說任意一條路徑上不會出現連續的紅色結點（黑色結點的孩子顏色不做要求）
4. 對于任意一個結點，從結點到這棵樹所有空結點的簡單路徑上，均包含相同數量的黑色結點

依靠它的幾條規則，從同一結點出發紅黑樹沒有一條路徑會比其他路徑長出2倍，因而也是接近平衡的。這是因為，由于從根到空結點的每條路徑都有相同數量的黑色結點，所以極限場景下，理論最短路徑就是全是黑色結點的路徑（設長度為bh），理論最長路徑是一黑一紅間隔組成，長度就是2bh了。也就是說，紅黑樹中任意一條從根到空結點的路徑x，都有bh <= x <= 2bh，確保了紅黑樹最長路徑不超過最短路徑的2倍了。

假設N是紅黑樹中結點數量，h是最短路徑長度，那么2^h -1 <= N <= 2^2h -1 ，推出h約等于logN，紅黑樹增刪查改最壞情況也就是走最長路徑2*logN，時間復雜度還是O(logN)。

這些規則保證了紅黑樹的平衡性，使得樹的高度保持在logN級別。相比于AVL樹，紅黑樹的平衡結構可以說更加“松散”，AVL樹嚴格要求了左右子樹高度差不超過1，但紅黑樹只要路徑長不超過2倍就行，但它們的效率還是相同的水平。

二、紅黑樹的實現

紅黑樹的結構

紅黑樹的基本結構，不需要AVL樹的平衡因子，而需要一個顏色成員:

enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root;
};

紅黑樹的插入

紅黑樹的插入新結點的過程是這樣的：

• 首先按照二叉搜索樹的規則找到應插入的位置，插入后我們需要判斷是否符合紅黑樹的規則。
• 如果是空樹插入，新增結點必須是黑色的，插入完成；如果是非空樹插入，新增結點必須是紅色的，因為如果非空樹插入了黑色結點就會破壞規則4，這條規則是很難維護的。
• 非空樹插入紅色結點后，如果父親是黑色的，則不會破壞任何規則，插入完成。
• 非空樹插入紅色結點后，如果父親是紅色的，就破壞了規則“紅色結點的孩子必須是黑色”，此時需要下面進一步分析。

---

接下來，我們具體分析最后一條情況，又有幾種場景。下面稱新增結點為c，c的父親為p，p的父親為g，p的兄弟為u。c是紅色的，p也是紅色的，那么g一定是黑色的，這三者的顏色是確定的，所以關鍵是看u的狀態（下圖中只表示出cpgu結點，省略其他子樹）：

場景1：

u存在且為紅色。這種場景下，c保持紅色不變，使p和u都變成黑色，g變為紅色。這樣處理后，就能使包含p或u的路徑的黑色結點數量保持一致。

場景2：

u存在且為黑色 或 u不存在。u不存在，則c一定是新增結點；u存在且為黑，則c一定不是新增結點，而是新增結點插入在了c的子樹中通過場景1調整后使c變成了紅色。

這兩種情況下處理方式是一樣的，需要旋轉+變色處理，但是旋轉變色的方式，和AVL樹一樣仍需分情況討論：

• p是g的左，c是p的左。以g為旋轉點右單旋。然后把p變黑，g變紅。如圖
• p是g的右，c是p的右。以g為旋轉點左單旋。然后把p變黑，g變紅。如圖
• p是g的左，c是p的右。**先以p為旋轉點左單旋，再以g為旋轉點右單旋（左右雙旋）。然后把c變黑，g變紅。**如圖
• p是g的右，c是p的左。**先以p為旋轉點右單旋，再以g為旋轉點左單旋（右左雙旋）。然后把c變黑，g變紅。**如圖

紅黑樹的插入代碼實現：

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;cur->_parent = parent;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//p是g的左的情況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;}//u不存在或存在為黑色else //旋轉+變色{if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p是g的右的情況else{Node* uncle = grandfather->_left;//u存在且為紅色//變色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//u不存在或存在為黑色else //旋轉+變色{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

紅黑樹的驗證

驗證我們的紅黑樹是否合格，也就需要檢查是否滿足了那四條規則

• 規則1不用檢查，因為我們一開始就用了枚舉類型賦值
• 規則2檢查根結點顏色即可
• 規則3進行前序遍歷，遇到紅色結點就檢查它的父結點是不是紅色的
• 規則4，首先用一個refNum記錄最左路徑的黑色結點數量，進行前序遍歷，遍歷過程中用一個變量blackNum記錄到當前結點的黑色結點數量，遇到黑色結點就++blackNum，走到空就計算出了一條路徑的黑色結點數量。此時若blackNum與refNum不同，則規則4不滿足。

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){if (refNum != blackNum){cout << "存在黑色結點數量不相同的路徑！" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在連續的紅色結點！" << 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;}//參考值refNum記錄最左路徑的黑色結點數量int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){refNum++;}cur = cur->_left;}return Check(_root, 0, refNum);
}

本篇完，感謝閱讀~