C++進階：紅黑樹介紹及模擬實現

上次介紹了AVL樹：C++進階：AVL樹詳解及模擬實現（圖示講解旋轉過程）

今天就來緊接著來紅黑樹啦!!!

---

---

1.紅黑樹介紹

紅黑樹是一種自平衡的二叉搜索樹，它在每個節點上增加了一個表示顏色的存儲位，可以是紅色（Red）或黑色（Black）。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的從而保證了查找、插入和刪除操作的時間復雜度為$O(logN)$

約束規則

1. 每個結點是紅色或者黑色

2. 根節點是黑色

3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的（不能有連續的紅節點）

4. 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色結點

5. 葉子節點（NIL節點）是黑色的(此處的葉子結點指的是空結點)

2.項目文件規劃

頭文件RBTree.h：進行模擬的編寫

源文件test.cpp：進行測試，檢查代碼邏輯是否滿足期望

3.整體框架（節點和Tree）

enum Colour//使用枚舉來定義，后面模擬哈希時也會用到類似的
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;//左節點RBTreeNode<K, V>* _right;//右節點RBTreeNode<K, V>* _parent;//父親節點Colour _col;//顏色，紅和黑嘛pair<K,V> _kv;//節點里存pairRBTreeNode(const pair<K, V>& kv)//都直接在初始化列表里初始化了:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//這里新插入的節點一定要是紅色，黑色的話會直接破壞規則{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;//名字太長了，叫Node也更好理解
public:private:Node* _root = nullptr;//給上缺省值
};

4.RBL樹的新節點插入

基本步驟：

1. 查找插入位置： 首先，我們需要找到新節點應該插入的位置。從根節點開始，按照二叉搜索樹的性質，逐級向左或向右比較鍵值，直到找到一個合適的位置。

2. 插入新節點： 找到插入位置后，我們創建一個新的節點，顏色為紅，并將其插入到樹中。如果樹為空，則新節點成為樹的根節點。否則，將新節點插入到合適的位置，使得樹仍然保持二叉搜索樹的性質。

3. 插入后有需要變化時情況很多，下面具體分析

因為新節點的默認顏色是紅色，因此：如果其雙親節點的顏色是黑色，沒有違反紅黑樹任何性質，則不需要調整；但當新插入節點的雙親節點顏色為紅色時，就違反了性質三不能有連在一起的紅色節點，此時需要對紅黑樹分情況來討論：

如果新插入節點的父親節點是黑，那根本不會違反規則，如果要調整只有如下情況：

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); //這是默認紅色的if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//新節點鏈接成功了while (parent != nullptr && parent->_col == RED)//父親節點存在且是紅進來，黑的直接滿足不用調整{//這里進行處理}_root->_col = BLACK;//最后直接改根節點，不用再具體考慮return true;}

4.1 叔叔節點存在且為紅

以下步驟來調整：

1. 將父節點和叔叔節點都改為黑色。
2. 將祖父節點改為紅色。
3. 將當前節點指向祖父節點，并將祖父節點設為當前節點的父節點(開始向上走)。

4.2 叔叔節點不存在

如果u節點不存在，則cur一定是新插入節點，因為如果cur不是新插入節點則cur和p一定有一個節點的顏色是黑色，就不滿足性質4: 每條路徑黑色節點個數相同。

1. p為g的左孩子，cur為p的左孩子，則進行右單旋轉

p為g的右孩子，cur為p的右孩子，則進行左單旋轉

2. p、g變色—>p變黑，g變紅

void RotateL(Node* parent)//左旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent)//右旋{++rotateSize;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}

4.3叔叔節點存在而且為黑（單旋情況，左子樹的左，和右子樹的右）

如果u節點存在，則其一定是黑色的，那么cur節點原來的顏色一定是黑色的現在看到其是紅色的原因是因為cur的子樹在調整的過程中將cur節點的顏色由黑色改成紅色

4.4叔叔節點存在而且為黑（雙旋情況，左子樹的右，和右子樹的左）

p為g的左孩子，cur為p的右孩子，左右雙旋+變色
p為g的右孩子，cur為p的左孩子，右左雙旋 +變色

4.5完整版Insert（）

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); //這是默認紅色的if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//新節點鏈接成功了while (parent != nullptr && parent->_col == RED)//父親節點存在且是紅進來，黑的直接滿足不用調整{Node* grandfather = parent->_parent;//接下來分兩種：parent是grandfather左或者右if (parent == grandfather->_left)//左{Node* uncle = grandfather->_right;//情況一：叔叔存在且為紅if (uncle && uncle->_col == RED){//先變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續往上走cur = grandfather;parent = cur->_parent;}else//情況二：叔叔不存在或者存在且為黑{if (cur == parent->_left)//cur在parent左，單旋{//       g//    p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在parent右，雙旋{//       g//    p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}//情況二一旦旋轉完了，不用向上了break;}else//parent是grandfather右{Node* uncle = grandfather->_left;// 情況一：叔叔存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else// 情況二：叔叔不存在或者存在且為黑{// 旋轉+變色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}break;}}_root->_col = BLACK;//最后直接改根節點，不用再具體考慮return true;}

---

5.中序方便過會測試

	void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first<< endl;_InOrder(root->_right);}

6.編寫函數看是否滿足要求

就從規定出發：

1. 根節點不是黑的不滿足
2. 不是每條路徑的黑色節點數量都相同
3. 存在連續的紅節點了

這些都是不滿足要求

	bool IsBalance(){if (_root->_col == RED){return false;}//這里我們先算一條路徑的黑色節點數量，作為參考int ref = 0;Node* cur = _root;while (cur){if(cur->_col==BLACK)ref++;cur = cur->_left;//就求最左路徑}return Check(_root, 0, ref);}bool Check(Node* cur, int blackNum, int ref){if (cur == nullptr)//==nullptr 說明一條路徑走完了{if (blackNum != ref){cout << "黑色節點的數量不相等" << endl;return false;}return true;}//這里開始檢查沒有連續的紅，就看每個cur節點和他的父親就行if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在連續的紅色節點" << endl;return false;}if (cur->_col == BLACK){blackNum++;}return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);//遞歸進去找}

IsBalance() 函數首先檢查根節點的顏色是否為紅色，如果是，則不滿足紅黑樹的性質。然后，通過調用 Check() 函數來遞歸檢查每個節點，確保在每條路徑上沒有連續的紅色節點，并統計路徑上的黑色節點數量，最后與參考值進行比較。

Check() 函數中，遞歸遍歷每個節點，并檢查其顏色。如果當前節點為紅色，并且其父節點也為紅色，則說明存在連續的紅色節點，不滿足紅黑樹的性質。如果當前節點為黑色，則增加黑色節點計數器。遞歸地對當前節點的左右子節點進行檢查，直到遍歷完整棵樹的所有路徑。

通過這樣的檢查，我們可以驗證紅黑樹是否滿足性質，從而確認樹的平衡性。

---

7.測試

void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15};RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;
}

---

8.全部代碼

8.1 RBTree.h

#pragma onceenum Colour//使用枚舉來定義，后面模擬哈希時也會用到類似的
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;//左節點RBTreeNode<K, V>* _right;//右節點RBTreeNode<K, V>* _parent;//父親節點Colour _col;//顏色，紅和黑嘛pair<K,V> _kv;//節點里存pairRBTreeNode(const pair<K, V>& kv)//都直接在初始化列表里初始化了:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//這里新插入的節點一定要是紅色，黑色的話會直接破壞規則{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;//名字太長了，叫Node也更好理解
public: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); //這是默認紅色的if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//新節點鏈接成功了while (parent != nullptr && parent->_col == RED)//父親節點存在且是紅進來，黑的直接滿足不用調整{Node* grandfather = parent->_parent;//接下來分兩種：parent是grandfather左或者右if (parent == grandfather->_left)//左{Node* uncle = grandfather->_right;//情況一：叔叔存在且為紅if (uncle && uncle->_col == RED){//先變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續往上走cur = grandfather;parent = cur->_parent;}else//情況二：叔叔不存在或者存在且為黑{if (cur == parent->_left)//cur在parent左，單旋{//       g//    p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur在parent右，雙旋{//       g//    p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}//情況二一旦旋轉完了，不用向上了break;}else//parent是grandfather右{Node* uncle = grandfather->_left;// 情況一：叔叔存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else// 情況二：叔叔不存在或者存在且為黑{// 旋轉+變色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(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;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent)//右旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first<< endl;_InOrder(root->_right);}bool IsBalance(){if (_root->_col == RED){return false;}//這里我們先算一條路徑的黑色節點數量，作為參考int ref = 0;Node* cur = _root;while (cur){if(cur->_col==BLACK)ref++;cur = cur->_left;//就求最左路徑}return Check(_root, 0, ref);}bool Check(Node* cur, int blackNum, int ref){if (cur == nullptr)//==nullptr 說明一條路徑走完了{if (blackNum != ref){cout << "黑色節點的數量不相等" << endl;return false;}return true;}//這里開始檢查沒有連續的紅，就看每個cur節點和他的父親就行if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在連續的紅色節點" << endl;return false;}if (cur->_col == BLACK){blackNum++;}return Check(cur->_left, blackNum, ref)&& Check(cur->_right, blackNum, ref);//遞歸進去找}private:Node* _root = nullptr;//給上缺省值
};void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15};RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;
}

8.2 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;#include"RBTree.h"int main()
{TestRBTree1();return 0;
}

---

今天就到這里啦！！