1. 紅?樹(shù)的概念

紅?樹(shù)是?棵?叉搜索樹(shù)，他的每個(gè)結(jié)點(diǎn)增加?個(gè)存儲(chǔ)位來(lái)表?結(jié)點(diǎn)的顏?，可以是紅?或者??。通過(guò)對(duì)任何?條從根到葉?的路徑上各個(gè)結(jié)點(diǎn)的顏?進(jìn)?約束，紅?樹(shù)確保沒(méi)有?條路徑會(huì)?其他路徑?出2倍，因?是接近平衡的

1.1 紅?樹(shù)的規(guī)則：

1. 每個(gè)結(jié)點(diǎn)不是紅?就是??
2. 根結(jié)點(diǎn)是??的
3. 如果?個(gè)結(jié)點(diǎn)是紅?的，則它的兩個(gè)孩?結(jié)點(diǎn)必須是??的，也就是說(shuō)任意?條路徑不會(huì)有連續(xù)的紅?結(jié)點(diǎn)。
4. 對(duì)于任意?個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有NULL結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)量的??結(jié)點(diǎn)說(shuō)明：《算法導(dǎo)論》等書(shū)籍上補(bǔ)充了?條每個(gè)葉?結(jié)點(diǎn)(NIL)都是??的規(guī)則。他這?所指的葉?結(jié)點(diǎn)不是傳統(tǒng)的意義上的葉?結(jié)點(diǎn)，?是我們說(shuō)的空結(jié)點(diǎn)，有些書(shū)籍上也把NIL叫做外部結(jié)點(diǎn)。NIL是為了?便準(zhǔn)確的標(biāo)識(shí)出所有路徑，《算法導(dǎo)論》在后續(xù)講解實(shí)現(xiàn)的細(xì)節(jié)中也忽略了NIL結(jié)點(diǎn)，所以我們知道?下這個(gè)概念即可。

這棵樹(shù)的路徑數(shù)為9.

引入NIL可以有效防止我們數(shù)錯(cuò)路徑數(shù)

1.2 思考?下，紅?樹(shù)如何確保最?路徑不超過(guò)最短路徑的2倍的？

? 由規(guī)則4可知，從根到NULL結(jié)點(diǎn)的每條路徑都有相同數(shù)量的??結(jié)點(diǎn)，所以極端場(chǎng)景下，最短路徑就就是全是??結(jié)點(diǎn)的路徑，假設(shè)最短路徑?度為bh(black height)。
? 由規(guī)則2和規(guī)則3可知，任意?條路徑不會(huì)有連續(xù)的紅?結(jié)點(diǎn)，所以極端場(chǎng)景下，最?的路徑就是???紅間隔組成，那么最?路徑的?度為2bh。
? 綜合紅?樹(shù)的4點(diǎn)規(guī)則??，理論上的全?最短路徑和???紅的最?路徑并不是在每棵紅?樹(shù)都存在的。假設(shè)任意?條從根到NULL結(jié)點(diǎn)路徑的?度為x，那么bh <= h <= 2bh。

1.3 紅?樹(shù)的效率：

假設(shè)N是紅?樹(shù)樹(shù)中結(jié)點(diǎn)數(shù)量，h最短路徑的?度，那么 2 ?, 由此推出。h 1 <= N < 2 ?2?h 1
h ≈ logN ，也就是意味著紅?樹(shù)增刪查改最壞也就是?最?路徑 2 ? logN ，那么時(shí)間復(fù)雜度還是O(logN)紅?樹(shù)的表達(dá)相對(duì)AVL樹(shù)要抽象?些，AVL樹(shù)通過(guò)?度差直觀的控制了平衡。紅?樹(shù)通過(guò)4條規(guī)則的顏?約束，間接的實(shí)現(xiàn)了近似平衡，他們效率都是同?檔次，但是相對(duì)??，插?相同數(shù)量的結(jié)點(diǎn)，紅?樹(shù)的旋轉(zhuǎn)次數(shù)是更少的，因?yàn)樗麑?duì)平衡的控制沒(méi)那么嚴(yán)格。

2. 紅?樹(shù)的實(shí)現(xiàn)

2.1 紅?樹(shù)的結(jié)構(gòu)

// 枚舉值表?顏?
enum Colour
{RED,BLACK
};
// 這?我們默認(rèn)按key/value結(jié)構(gòu)實(shí)現(xiàn)
template<class K, class V>
struct RBTreeNode
{
// 這?更新控制平衡也要加?parent指針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;
};

這一塊的結(jié)構(gòu)是跟AVL樹(shù)是一樣的，只是這里少了平衡因子，多了一個(gè)color

2.2 紅?樹(shù)的插?

2.2.1 紅?樹(shù)樹(shù)插??個(gè)值的?概過(guò)程

1. 插??個(gè)值按?叉搜索樹(shù)規(guī)則進(jìn)?插?，插?后我們只需要觀察是否符合紅?樹(shù)的4條規(guī)則。
2. 如果是空樹(shù)插?，新增結(jié)點(diǎn)是??結(jié)點(diǎn)。如果是?空樹(shù)插?，新增結(jié)點(diǎn)必須紅?結(jié)點(diǎn)，因?yàn)?空樹(shù)插?，新增??結(jié)點(diǎn)就破壞了規(guī)則4，規(guī)則4是很難維護(hù)的。
3. ?空樹(shù)插?后，新增結(jié)點(diǎn)必須紅?結(jié)點(diǎn)，如果?親結(jié)點(diǎn)是??的，則沒(méi)有違反任何規(guī)則，插?結(jié)束
4. ?空樹(shù)插?后，新增結(jié)點(diǎn)必須紅?結(jié)點(diǎn)，如果?親結(jié)點(diǎn)是紅?的，則違反規(guī)則3。進(jìn)?步分析，c是紅?，p為紅，g必為?，這三個(gè)顏?都固定了，關(guān)鍵的變化看u的情況，需要根據(jù)u分為以下?種情況分別處理。

說(shuō)明：下圖中假設(shè)我們把新增結(jié)點(diǎn)標(biāo)識(shí)為c (cur)，c的?親標(biāo)識(shí)為p(parent)，p的?親標(biāo)識(shí)為
g(grandfather)，p的兄弟標(biāo)識(shí)為u（uncle）。

2.2.2 情況1：變?

c為紅，p為紅，g為?，u存在且為紅，則將p和u變?，g變紅。在把g當(dāng)做新的c，繼續(xù)往上更新。分析：因?yàn)閜和u都是紅?，g是??，把p和u變?，左邊?樹(shù)路徑各增加?個(gè)??結(jié)點(diǎn)，g再變紅，相當(dāng)于保持g所在?樹(shù)的??結(jié)點(diǎn)的數(shù)量不變，同時(shí)解決了c和p連續(xù)紅?結(jié)點(diǎn)的問(wèn)題，需要繼續(xù)往上更新是因?yàn)?#xff0c;g是紅?，如果g的?親還是紅?，那么就還需要繼續(xù)處理；如果g的?親是??，則處理結(jié)束了；如果g就是整棵樹(shù)的根，再把g變回??。情況1只變?，不旋轉(zhuǎn)。所以?論c是p的左還是右，p是g的左還是右，都是上?的變?處理?式。

2.2.3 情況2：單旋+變?

c為紅，p為紅，g為?，u不存在或者u存在且為?，u不存在，則c?定是新增結(jié)點(diǎn)，u存在且為?，則c?定不是新增，c之前是??的，是在c的?樹(shù)中插?，符合情況1，變?將c從??變成紅?，更新上來(lái)的。
分析：p必須變?，才能解決，連續(xù)紅?結(jié)點(diǎn)的問(wèn)題，u不存在或者是??的，這?單純的變??法解決問(wèn)題，需要旋轉(zhuǎn)+變?。
g
p u
c
如果p是g的左，c是p的左，那么以g為旋轉(zhuǎn)點(diǎn)進(jìn)?右單旋，再把p變?，g變紅即可。p變成課這顆樹(shù)新的根，這樣?樹(shù)??結(jié)點(diǎn)的數(shù)量不變，沒(méi)有連續(xù)的紅?結(jié)點(diǎn)了，且不需要往上更新，因?yàn)閜的?親是??還是紅?或者空都不違反規(guī)則。
g
u p
c
如果p是g的右，c是p的右，那么以g為旋轉(zhuǎn)點(diǎn)進(jìn)?左單旋，再把p變?，g變紅即可。p變成課這顆樹(shù)新的根，這樣?樹(shù)??結(jié)點(diǎn)的數(shù)量不變，沒(méi)有連續(xù)的紅?結(jié)點(diǎn)了，且不需要往上更新，因?yàn)閜的?親是??還是紅?或者空都不違反規(guī)則。

2.2.4 情況2：雙旋+變?

c為紅，p為紅，g為?，u不存在或者u存在且為?，u不存在，則c?定是新增結(jié)點(diǎn)，u存在且為?，則c?定不是新增，c之前是??的，是在c的?樹(shù)中插?，符合情況1，變?將c從??變成紅?，更新上來(lái)的。
分析：p必須變?，才能解決，連續(xù)紅?結(jié)點(diǎn)的問(wèn)題，u不存在或者是??的，這?單純的變??法解決問(wèn)題，需要旋轉(zhuǎn)+變?。
g
p u
c

如果p是g的左，c是p的右，那么先以p為旋轉(zhuǎn)點(diǎn)進(jìn)?左單旋，再以g為旋轉(zhuǎn)點(diǎn)進(jìn)?右單旋，再把c變?，g變紅即可。c變成課這顆樹(shù)新的根，這樣?樹(shù)??結(jié)點(diǎn)的數(shù)量不變，沒(méi)有連續(xù)的紅?結(jié)點(diǎn)了，且不需要往上更新，因?yàn)閏的?親是??還是紅?或者空都不違反規(guī)則。

2.3 紅?樹(shù)的插?代碼實(shí)現(xiàn)

bool insert(const pair<k, v>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = Black;}//根節(jié)點(diǎn)Node* parent = nullptr;Node* cur = _root;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 false;}}//找到該插入的位置了cur = new Node(kv);cur->_parent = parent;if (cur->_kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;//鏈接curwhile (parent && parent->_col == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == Red)//叔叔節(jié)點(diǎn)存在并且為紅色{//			g//		p       u//  c grandfather->_col = Red;parent->_col = Black;uncle->_col = Black;cur = grandfather;parent = cur->_parent;}else//叔叔節(jié)點(diǎn)不存在{//			g//		p      //  c if (cur == parent->_left){RotateR(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//			g//		p      //			c RotateL(parent);RotateR(grandfather);cur->_col = Black;grandfather->_col = parent->_col = Red;}break;}}else//parent為grandfather的右邊{Node* uncle = grandfather->_left;if (uncle && uncle->_col == Red){//			g//		u       p//			cgrandfather->_col = Red;parent->_col = uncle->_col = Black;cur = grandfather;parent = cur->_parent;}else//uncle為空{//			g//		       p//				  cif (cur == parent->_right){RotateL(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//			g//		       p//			cRotateR(parent);RotateL(grandfather);grandfather->_col = Red;cur->_col = Black;}break;}}}_root->_col = Black;return true;
}

2.4 紅?樹(shù)的查找

Node* find(const pair<k,v>& kv)
{Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){cur = cur->_right;}else if (kv.first < cur->_kv.first){cur = cur->_left;}elsereturn cur;}return nullptr;
}

3 紅?樹(shù)的驗(yàn)證

這?獲取最?路徑和最短路徑，檢查最?路徑不超過(guò)最短路徑的2倍是不可?的，因?yàn)榫退銤M?這個(gè)條件，紅?樹(shù)也可能顏?不滿?規(guī)則，當(dāng)前暫時(shí)沒(méi)出問(wèn)題，后續(xù)繼續(xù)插?還是會(huì)出問(wèn)題的。所以我們還是去檢查4點(diǎn)規(guī)則，滿?這4點(diǎn)規(guī)則，?定能保證最?路徑不超過(guò)最短路徑的2倍。

1. 規(guī)則1枚舉顏?類(lèi)型，天然實(shí)現(xiàn)保證了顏?不是??就是紅?。
2. 規(guī)則2直接檢查根即可
3. 規(guī)則3前序遍歷檢查，遇到紅?結(jié)點(diǎn)查孩?不太?便，因?yàn)楹?有兩個(gè)，且不?定存在，反過(guò)來(lái)檢查?親的顏?就?便多了。
4. 規(guī)則4前序遍歷，遍歷過(guò)程中?形參記錄跟到當(dāng)前結(jié)點(diǎn)的blackNum(??結(jié)點(diǎn)數(shù)量)，前序遍歷遇到??結(jié)點(diǎn)就++blackNum，?到空就計(jì)算出了?條路徑的??結(jié)點(diǎn)數(shù)量。再任意?條路徑??結(jié)點(diǎn)數(shù)量作為參考值，依次?較即可。

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){// 前序遍歷?到空時(shí)，意味著?條路徑?完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在??結(jié)點(diǎn)的數(shù)量不相等的路徑" << endl;return false;}return true;}// 檢查孩?不太?便，因?yàn)楹?有兩個(gè)，且不?定存在，反過(guò)來(lái)檢查?親就?便多了if (root->_col == Red && root->_parent->_col == Red){cout << root->_kv.first << "存在連續(xù)的紅色結(jié)點(diǎn)" << 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);
}

這一塊的實(shí)現(xiàn)還是有價(jià)值的，我的建議是大家都理解一下

4 總的代碼

#include<iostream>
using namespace std;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:bool insert(const pair<k, v>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = Black;}//根節(jié)點(diǎn)Node* parent = nullptr;Node* cur = _root;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 false;}}//找到該插入的位置了cur = new Node(kv);cur->_parent = parent;if (cur->_kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;//鏈接curwhile (parent && parent->_col == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == Red)//叔叔節(jié)點(diǎn)存在并且為紅色{//			g//		p       u//  c grandfather->_col = Red;parent->_col = Black;uncle->_col = Black;cur = grandfather;parent = cur->_parent;}else//叔叔節(jié)點(diǎn)不存在{//			g//		p      //  c if (cur == parent->_left){RotateR(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//			g//		p      //			c RotateL(parent);RotateR(grandfather);cur->_col = Black;grandfather->_col = parent->_col = Red;}break;}}else//parent為grandfather的右邊{Node* uncle = grandfather->_left;if (uncle && uncle->_col == Red){//			g//		u       p//			cgrandfather->_col = Red;parent->_col = uncle->_col = Black;cur = grandfather;parent = cur->_parent;}else//uncle為空{//			g//		       p//				  cif (cur == parent->_right){RotateL(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//			g//		       p//			cRotateR(parent);RotateL(grandfather);grandfather->_col = Red;cur->_col = Black;}break;}}}_root->_col = Black;return true;}void RotateR(Node* parent)//右旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pparent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;subL->_parent = pparent;}else{pparent->_right = subL;subL->_parent = pparent;}}}void RotateL(Node* parent)//左旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pparent = parent->_parent;parent->_parent = subR;subR->_left = parent;if (pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;subR->_parent = pparent;}else{pparent->_right = subR;subR->_parent = pparent;}}}void inorder(){_inorder(_root);}Node* find(const pair<k,v>& kv){Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){cur = cur->_right;}else if (kv.first < cur->_kv.first){cur = cur->_left;}elsereturn cur;}return nullptr;}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍歷?到空時(shí)，意味著?條路徑?完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在??結(jié)點(diǎn)的數(shù)量不相等的路徑" << endl;return false;}return true;}// 檢查孩?不太?便，因?yàn)楹?有兩個(gè)，且不?定存在，反過(guò)來(lái)檢查?親就?便多了if (root->_col == Red && root->_parent->_col == Red){cout << root->_kv.first << "存在連續(xù)的紅色結(jié)點(diǎn)" << 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:void _inorder(Node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_inorder(root->_right);}Node* _root = nullptr;
};

左旋右旋完全跟AVL樹(shù)一樣，這里我就不在多講了，如果還有問(wèn)題大家可以看一下我前一篇博客《AVL的實(shí)現(xiàn)》

5 簡(jiǎn)單總結(jié)

紅黑樹(shù)相較于AVL樹(shù)抽象許多，但實(shí)際代碼實(shí)現(xiàn)并不復(fù)雜，所以這一塊的難點(diǎn)在于理解插入的過(guò)程，而插入的過(guò)程與uncle節(jié)點(diǎn)緊密相關(guān)，如果想要學(xué)好紅黑樹(shù)，uncle使我們必須要掌握的。