數據結構（六)——紅黑樹及模擬實現

前言

紅黑樹的概念及性質

紅黑樹的效率

紅黑樹的結構

紅黑樹的插入

變色不旋轉

單旋+變色

雙旋+變色

插入代碼如下所示：

紅黑樹的查找

紅黑樹的驗證

紅黑樹代碼如下所示：

小結

前言

在前面的文章我們介紹了AVL這一棵完全二叉搜索樹，我們分析后發現AVL樹查找的時間復雜度是O（logN），說明這是一個很優秀的數據結構，但是在底層實現我們發現，AVL樹為了維持它的性質，是需要進行頻繁的旋轉的，這樣會造成不必要的消耗，那么有沒有一種數據結構既可保證它的時間復雜度為O(logN)，又能避免頻繁的旋轉呢？這就是我們今天要介紹的紅黑樹，學習了紅黑樹之后我們將用紅黑樹作為底層，去封裝實現一個模擬的map和set，下面讓我們一起來學習吧。

參考文章：

據結構（五)——AVL樹（平衡二叉搜索樹)

紅黑樹的概念及性質

首先我們要知道什么是紅黑樹，與AVL樹相比，紅黑樹的節點多了一個標志符號，這個標志符號表示節點的顏色，我們這里用枚舉來表示，通過控制節點的顏色來判平衡以及判斷是否需要旋轉。由于紅黑樹的旋轉不像AVL樹那么頻繁，所以它是一顆不完全平衡二叉搜索樹。

下面我們引入路徑的概念，我們把從根節點開始，一直到空節點的一條路線稱為路徑

它的規則如下所示：

規則一：根節點必須是黑色，其余節點的顏色不是黑色就是紅色

規則二：每個紅色節點的左右子樹必須是紅色的，即：不存在連續的紅色節點

規則三：每條路徑的黑色節點數量是相同的，其中我們把空節點視為黑色節點

規則四：最長路徑的節點數量不超過最長路徑節點數量的二倍

分析上面的規則我們發現，其中最關鍵也是最難維護的就是規則三，我們發現，在極端場景下，最短路徑就是全為黑色節點的路徑，最長路徑就是紅黑間隔的路徑，所以維護好了規則三，規則四自然就實現了

紅黑樹的效率

由于有規則四的存在，我們設紅黑樹最短路徑的節點數量是h，那么最長路徑的節點數量就是2*h，我們設每條路徑上黑色節點的數量是N，那么他們應該滿足： $2^{h}-1<=N<2^{2*h}-1$ ，也就是說，如果我們要在紅黑樹當中進行增刪查改，最少要走的長度是 $2^{h}-1$ ，查找的次數就是log(N)，最壞也就是查找2*log(N)，分析下來，它的時間復雜度還是log(N)。

紅黑樹的結構

從上面的分析中我們知道，紅黑樹的大致框架與AVL樹相似，只不過將平衡因子改成了用枚舉表示的顏色，后續我們也是通過控制顏色來判平衡，因此紅黑樹的結構如下所示：

enum Colour
{BLACK,RED
};
template<class K, class V>
struct RBTreeNode
{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;
};

紅黑樹的插入

我們來分析紅黑樹的插入過程，首先由于它是一顆搜索樹，所以按照搜索樹的規則進行插入，更改插入結點的顏色，然后我們向上進行調整。

對于插入節點的顏色，我們發現，如果我們插入黑色，那么就在當前路徑上增加了一個黑色節點，不符合每條路徑上黑色節點數量相同這一規則，所以我們插入節點的顏色應該為紅色。代碼如下所示：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{cout << "插入值已經存在，請重新插入" << endl;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;
}

當我們插入紅色節點后，會出下面幾種情況：

情況一：父節點為黑色，不違反紅黑樹的規則，那么就停止向上調整

情況二：父節點為紅色，違反規則，那么就需要向上調整

接下來我們重點分析情況二。由于不能有兩個連續的紅色節點，所以我們應當把父節點變成黑色，但是將父節點變成黑色后我們就在當前路徑上憑空增加了一個黑色節點，這樣破壞了黑色節點數量相同這一規則，那么我們就需要調整其他路徑上黑色節點的數量，如果是這樣的話，是不符合我們的預期的，我們再仔細觀察紅黑樹的結構，我們把父節點的父節點定義為grandfather(祖父節點)，那么祖父節點的另一個子節點稱為uncle(叔節點)，我們發現，無論什么情況，只要涉及到需要向上調整，祖父節點總是黑色的，此時，如果叔節點存在且為紅色的話，我們就只需要將父節點和叔節點顏色變為黑色，再將祖父節點變為紅色，這樣就解決了這個問題；如果叔節點不存在或者存在且為空節點，那么此時我們就需要做特殊處理。

通過上述分析，我們總結一下紅黑樹的插入過程：

第一步：插入節點。按照二叉搜索樹的規則插入節點，鏈接父節點，將插入節點的顏色改成紅色，如果是根節點，就變為黑色。

第二步：向上調整黑色節點的數量，讓其滿足紅黑樹的規則。

接下來我們逐步來分析向上調整。

根據上面的分析我們知道，我們可以根據uncle節點的有無以及顏色，可以分為下面兩種情況：

情況一：uncle節點存在且顏色為紅色

情況二：uncle節點存在且為黑色或者uncle不存在

如下圖所示：

對于情況一，我們只需要將父節點和uncle節點顏色變為黑色，然后再將祖父節點顏色變為紅色，然后向上更新parent節點和grandfather節點，因此我們需要一個循環，循環結束的條件是：parent為空或者parent的顏色為黑色。

對于情況二，我們發現這種情況又需要分為兩種場景，一種是插入節點是parent的左節點，另一種是插入節點是parent的右節點，這兩種情景無論我們怎么變色都沒有辦法滿足紅黑樹的規則，為此我們需要尋找一種新的解決辦法。

回到紅黑樹的定義，我們知道，紅黑樹是一顆不完全平衡二叉搜索樹，從前面的AVL樹我們知道，要成為一顆平衡樹，我們要做的就是旋轉，而旋轉分為左旋和右旋，那么我們嘗試將AVL樹的旋轉帶入紅黑樹當中，那么對于parent與cur都位于同一側節點的這種情況，我們使用單旋，對于parent與cur位于不同一側節點的這種情況，我們使用雙旋。

綜上所述，紅黑樹的插入可以分為以下三種不同的情況：

變色不旋轉

條件：grandfather為黑，parent與cur為紅色，uncle存在且為紅。

解決辦法：parent與cur變為黑色，grandfather變為紅色，然后再將grandfather當成新的cur，繼續向上更新。

分析：由于cur與parent都是紅色，所以我們應該把parent變為黑色，這樣就在當前節點憑空增加了一個黑色節點，從而導致黑色節點失衡；由于uncle是紅色，為了讓黑色節點數量保持平衡，所以我們需要把uncle也變成黑色，然后讓grandfather變為紅色。

單旋+變色

條件：grandfather為黑色，parent與cur為紅色，uncle不存在或者uncle存在且為黑，并且parent與cur位于同一側

解決辦法：以grandfather節點為旋轉點，如果位于左側則右旋；如果位于右側則左旋，旋轉結束后讓parent變為黑色，grandfather變成紅色

分析：由于uncle是黑色節點，如果我們直接按照第一種情況進行變色，那么就會導致uncle這條路徑上始終少一個節點，這樣導致節點失衡，所以我們要先進行旋轉，旋轉結束后parent成為了cur與grandfather的父節點，為了讓黑色節點數量保持平衡，我們需要讓parent變成黑色，讓grandfather變成紅色

雙旋+變色

條件：grandfather為黑色，parent與cur為紅色，uncle不存在或者uncle存在且為黑，并且parent與cur位于不同側

解決辦法：首先以parent為旋轉點進行一次旋轉，然后再以grandfather為旋轉點進行一次旋轉，旋轉結束后讓cur變成黑色，讓grandfather變成紅色。

分析：由于uncle是黑節點，cur與parent位于相反的兩側，如果我們旋轉一次，結果還是這種情況，所以我們需要進行兩次旋轉，旋轉結束后，為了保持黑色節點數量的平衡，我們需要將cur變成黑色，讓grandfather變成紅色

插入代碼如下所示：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{cout << "插入值已經存在，請重新插入" << endl;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}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{if (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;if (subRL)subRL->_parent = parent;Node* grandfather = parent->_parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (grandfather->_left == parent){grandfather->_left = subR;}else{grandfather->_right = subR;}subR->_parent = grandfather;}}
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* grandfather = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (grandfather->_left == parent){grandfather->_left = subL;}else{grandfather->_right = subL;}subL->_parent = grandfather;}
}

旋轉邏輯在這篇文章介紹：

數據結構（五)——AVL樹（平衡二叉搜索樹)

紅黑樹的查找

紅黑樹的查找與二叉搜索樹相同，都是通過遍歷比較節點值與目標值的大小知道找到目標值所在的節點然后返回或者直到遍歷完這顆樹為止，其代碼如下所示：

Node* Find(const pair<K, V>& kv)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return cur;}}cout << "目標值不存在" << endl;return nullptr;
}

紅黑樹的驗證

前面我們驗證紅黑樹時使用的方法是驗證平衡因子以及左右子樹高度差，實際上我們是按照AVL樹的規則進行驗證的，那么對于紅黑樹而言我們要通過它的規則進行驗證，檢查最長路徑不超過最短路徑的二倍嗎？這樣顯然是不現實的，那么我們是通過什么方法去驗證呢？我們還是通過遞歸去驗證，不同的是我們引入了一個新的參數——參考值，這個值是用來記錄從根節點到空節點這一整條路徑中黑色節點的數量的，我們用這個值作為參考去比較其他路徑上黑色節點的數量是否與這個值相同。其代碼如下所示：

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);
}

紅黑樹代碼如下所示：

enum Colour
{BLACK,RED
};
template<class K, class V>
struct RBTreeNode
{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:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{cout << "插入值已經存在，請重新插入" << endl;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}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{if (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;if (subRL)subRL->_parent = parent;Node* grandfather = parent->_parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (grandfather->_left == parent){grandfather->_left = subR;}else{grandfather->_right = subR;}subR->_parent = grandfather;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* grandfather = parent->_parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (grandfather->_left == parent){grandfather->_left = subL;}else{grandfather->_right = subL;}subL->_parent = grandfather;}}Node* Find(const pair<K, V>& kv){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return cur;}}cout << "目標值不存在" << endl;return nullptr;}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);}
private:Node* _root = nullptr;
};