一、紅黑樹(shù)的概念

??紅黑樹(shù)，是一種二叉搜索樹(shù)，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。

---

二、紅黑樹(shù)的性質(zhì)

1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
2. 根節(jié)點(diǎn)是黑色的
3. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的，即樹(shù)中沒(méi)有連續(xù)的紅色節(jié)點(diǎn)
4. 對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)，即每條路徑的黑色節(jié)點(diǎn)數(shù)量相等
5. 每個(gè)葉子結(jié)點(diǎn)(這里的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn)，也叫做NIL節(jié)點(diǎn) ）都是黑色的

??紅黑樹(shù)中第三和第四條規(guī)則構(gòu)成互斥，極限的最短一定是全黑，極限的最長(zhǎng)一定是一黑一紅 。

---

三、紅黑樹(shù)節(jié)點(diǎn)的定義

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pair<K, V> _kv;		//節(jié)點(diǎn)的值域Colour _col;		//節(jié)點(diǎn)的顏色RBTreeNode<K, V>* _left;	//節(jié)點(diǎn)的左孩子RBTreeNode<K, V>* _right;	//節(jié)點(diǎn)的右孩子RBTreeNode<K, V>* _parent;	//節(jié)點(diǎn)的雙親
};

---

四、紅黑樹(shù)的插入操作

??紅黑樹(shù)是在二叉搜索樹(shù)的基礎(chǔ)上加上其平衡限制條件，因此紅黑樹(shù)的插入可分為兩步：一、按照二叉搜索的樹(shù)規(guī)則插入新節(jié)點(diǎn)。二、檢測(cè)新節(jié)點(diǎn)插入后，紅黑樹(shù)的性質(zhì)是否造到破壞。

??因?yàn)樾鹿?jié)點(diǎn)的默認(rèn)顏色是紅色，如果其雙親節(jié)點(diǎn)的顏色是黑色，沒(méi)有違反紅黑樹(shù)任何性質(zhì)，則不需要調(diào)整；但當(dāng)新插入節(jié)點(diǎn)的雙親節(jié)點(diǎn)顏色為紅色時(shí)，就違反了性質(zhì)三（不能有連續(xù)的紅色節(jié)點(diǎn)），此時(shí)需要對(duì)紅黑樹(shù)分情況來(lái)討論。

---

情況一: cur為紅，p為紅，g為黑，u存在且為紅

??cur為當(dāng)前節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)。此處看到的樹(shù)，可能是一顆完整的樹(shù)，但是也有可能是一顆子樹(shù)。

??解決方式是將將p,u改為黑，g改為紅。繼續(xù)把g當(dāng)成cur，g是根節(jié)點(diǎn)，需要將g改為黑色，如果g是子樹(shù)且g的雙親顏色為紅色，則需要繼續(xù)向上調(diào)整。

---

情況二: cur為紅，p為紅，g為黑，u不存在/u存在且為黑

??如果u節(jié)點(diǎn)不存在，那么cur一定為新插入的節(jié)點(diǎn)，否則就違反性質(zhì)4。如果u節(jié)點(diǎn)存在，則一定是黑色的，cur之前也是黑色的，因?yàn)樾略龉?jié)點(diǎn)是a、b節(jié)點(diǎn)，所以現(xiàn)在它是紅色。

??解決方式：如果p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)。然后再將p變黑，g變紅。

---

情況三: cur為紅，p為紅，g為黑，u不存在/u存在且為黑

??解決方式：如果p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)；如果p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)。旋轉(zhuǎn)后就轉(zhuǎn)變?yōu)榱饲闆r二。

---

總結(jié)

??在這三種情況中，都有cur為紅，p為紅，g為黑，可以看出紅黑樹(shù)的關(guān)鍵是叔叔。U存在且為紅則變色繼續(xù)往上處理，U不存在或?yàn)楹?#xff0c;則旋轉(zhuǎn)加變色。

??情況二和情況三的主要區(qū)別是單旋和雙旋的不同。從圖中可以看出，當(dāng)p g cur為一條直線的時(shí)候，也就是情況二，單旋即可；p g cur 為一條折線的時(shí)候，也就是情況三，需要雙旋。

---

代碼實(shí)現(xiàn)

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);//新節(jié)點(diǎn)的默認(rèn)顏色是紅色，因?yàn)槿绻潆p親節(jié)點(diǎn)的顏色是黑色，沒(méi)有違反紅黑樹(shù)任何性質(zhì)，則不需要調(diào)整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* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);// 關(guān)鍵看叔叔if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情況一 : uncle存在且為紅，變色+繼續(xù)往上處理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 繼續(xù)往上處理cur = grandfater;parent = cur->_parent;}// 情況二+三：uncle不存在 + 存在且為黑else{// 情況二：右單旋+變色//     g //   p   u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情況三：左右單旋+變色//     g //   p   u//     cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;// 情況一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 繼續(xù)往上處理cur = grandfater;parent = cur->_parent;}else{// 情況二：左單旋+變色//     g //   u   p//         cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情況三：右左單旋+變色//     g //   u   p//     cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

---

五、紅黑樹(shù)的驗(yàn)證

??紅黑樹(shù)的檢測(cè)分為兩步：一、檢測(cè)其是否滿足二叉搜索樹(shù)，這里只需要中序遍歷是否為有序序列即可。二、檢測(cè)其是否滿足紅黑樹(shù)的性質(zhì)。

public:bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根節(jié)點(diǎn)不是黑色" << endl;return false;}int benchmark = 0;return PrevCheck(_root, 0, benchmark);}
private:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}

---

五、紅黑樹(shù)的刪除

??紅黑樹(shù)的刪除過(guò)于復(fù)雜，可以參考 紅黑樹(shù)的刪除 這篇博客

---

六、紅黑樹(shù)與AVL樹(shù)的比較

??紅黑樹(shù)和AVL樹(shù)都是高效的平衡二叉樹(shù)，增刪改查的時(shí)間復(fù)雜度都是O($lo{g}_{2}N$)，紅黑樹(shù)不追求絕對(duì)平衡，其只需保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍，相對(duì)而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹(shù)更優(yōu)，而且紅黑樹(shù)實(shí)現(xiàn)比較簡(jiǎn)單，所以實(shí)際運(yùn)用中紅黑樹(shù)更多。

---

七、紅黑樹(shù)的應(yīng)用

??紅黑樹(shù)的應(yīng)用場(chǎng)景建議觀看這個(gè)視頻講解紅黑樹(shù)在linux中的3種應(yīng)用場(chǎng)景

八、紅黑樹(shù)模擬實(shí)現(xiàn)

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pair<K, V> _kv;Colour _col;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;
};template<class K, class V>
struct 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* 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);//新節(jié)點(diǎn)的默認(rèn)顏色是紅色，因?yàn)槿绻潆p親節(jié)點(diǎn)的顏色是黑色，沒(méi)有違反紅黑樹(shù)任何性質(zhì)，則不需要調(diào)整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* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);// 關(guān)鍵看叔叔if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情況一 : uncle存在且為紅，變色+繼續(xù)往上處理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 繼續(xù)往上處理cur = grandfater;parent = cur->_parent;}// 情況二+三：uncle不存在 + 存在且為黑else{// 情況二：右單旋+變色//     g //   p   u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情況三：左右單旋+變色//     g //   p   u//     cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;// 情況一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 繼續(xù)往上處理cur = grandfater;parent = cur->_parent;}else{// 情況二：左單旋+變色//     g //   u   p//         cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情況三：右左單旋+變色//     g //   u   p//     cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根節(jié)點(diǎn)不是黑色" << endl;return false;}// 黑色節(jié)點(diǎn)數(shù)量基準(zhǔn)值int benchmark = 0;return PrevCheck(_root, 0, benchmark);}private:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_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;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}
private:Node* _root = nullptr;
};