一、紅黑樹(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)出倆倍（即最長(zhǎng)路徑不超過(guò)最短路徑的兩倍，近似平衡），因而是接近平衡的。

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

1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
2. 根節(jié)點(diǎn)是黑色的
3. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)必須是黑色的（即任何路徑?jīng)]有連續(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)個(gè)數(shù)相同，這里的路徑包括空結(jié)點(diǎn)）
5. 每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn)，已經(jīng)不在是傳統(tǒng)的葉子結(jié)點(diǎn)了，圖中的NIL結(jié)點(diǎn)就是空結(jié)點(diǎn)）

這里對(duì)第四點(diǎn)做一補(bǔ)充說(shuō)明

對(duì)于下面這棵樹(shù)有11條路徑，而不是5條路徑，因?yàn)榭战Y(jié)點(diǎn)也包括在內(nèi)

如果不清楚上面的這一點(diǎn)，如果遇到下面這棵樹(shù)，可能會(huì)誤以為他是紅黑樹(shù)，實(shí)際上它不是紅黑樹(shù)。

如果我們不看每個(gè)空結(jié)點(diǎn)的話，它看上去有四條路徑，且每條路徑都只有兩個(gè)黑色結(jié)點(diǎn)，看上去好像是紅黑樹(shù)。但是實(shí)際上要包括空結(jié)點(diǎn)，且空結(jié)點(diǎn)是黑色的。所以一共有九條路徑，最左邊的一條路徑只有兩個(gè)黑色結(jié)點(diǎn)，其他路徑都有三個(gè)黑色結(jié)點(diǎn)。

第四點(diǎn)中說(shuō)的雖然是每個(gè)結(jié)點(diǎn)的每條路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)相同，但是由于每個(gè)結(jié)點(diǎn)的祖先的路徑是唯一確定的，所以我們只需要判斷從根節(jié)點(diǎn)到每個(gè)空結(jié)點(diǎn)上的路徑中黑色結(jié)點(diǎn)個(gè)數(shù)是否相同即可

那么為什么上面的性質(zhì)可以保證最長(zhǎng)路徑不超過(guò)最長(zhǎng)路徑的兩倍呢？

如下圖所示， 最長(zhǎng)路徑就是黑紅相間的情況，最短路徑就是全黑的情況。其他路徑都是在這兩者之間的，此時(shí)我們也不難看出最長(zhǎng)路徑不超過(guò)最短路徑的兩倍。如果最短路徑為N，那么最長(zhǎng)路徑就是2N-1，因?yàn)楦?jié)點(diǎn)一定是黑色的，最終的葉子結(jié)點(diǎn)也一定是黑色的。

三、紅黑樹(shù)和AVL樹(shù)對(duì)比

既然有了AVL樹(shù)，那么為什么要有紅黑樹(shù)呢？其實(shí)是因?yàn)锳VL樹(shù)太嚴(yán)格了。它要控制平衡就需要付出代價(jià)。而紅黑樹(shù)要求并不嚴(yán)格，綜合來(lái)看，紅黑樹(shù)的綜合性能其實(shí)更優(yōu)

	AVL樹(shù)	紅黑樹(shù)
高度對(duì)比	高度差不超過(guò)一	最長(zhǎng)路徑不超過(guò)最短路徑的兩倍
插入1000個(gè)值	logN---->10	2*logN---->20
插入10億個(gè)值	logN---->30	2*logN---->60

我們可以看到，雖然他們的高度有點(diǎn)差異，但是他們的效率都是同一個(gè)量級(jí)的，而且cpu的速度是非?？斓?#xff0c;這點(diǎn)效率對(duì)于cpu幾乎沒(méi)有任何區(qū)別

性能是同一量級(jí)的，但是AVL樹(shù)控制嚴(yán)格平衡是需要付出代價(jià)的，插入和刪除需要大量的旋轉(zhuǎn)。

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

1. 紅黑樹(shù)的結(jié)點(diǎn)定義

如下所示， 由于紅黑樹(shù)有紅色結(jié)點(diǎn)和黑色結(jié)點(diǎn)兩種顏色。所以不妨我們使用一個(gè)枚舉類(lèi)型來(lái)進(jìn)行表示。紅黑樹(shù)里面我們需要有一個(gè)pair類(lèi)型來(lái)進(jìn)行存儲(chǔ)key和value類(lèi)型的數(shù)據(jù)。然后我們定義三個(gè)指針，分別指向父親，左孩子，右孩子。最后定義其的顏色。在構(gòu)造函數(shù)中，我們將其的顏色默認(rèn)設(shè)置為紅色。

設(shè)置為紅色是比較有講究的。那是因?yàn)槲覀兇蠖鄶?shù)場(chǎng)景下都是去創(chuàng)建一個(gè)新節(jié)點(diǎn)去插入的。如果我們插入的這個(gè)新結(jié)點(diǎn)是黑色的話，那么造成的后果就是違反了規(guī)則4，即每條路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)相同，顯然這種情況要進(jìn)行補(bǔ)救的話是十分麻煩的。還不如去插入紅色結(jié)點(diǎn)，如果插入的是紅色結(jié)點(diǎn)的話，僅僅有可能會(huì)違反規(guī)則3，也就是紅色結(jié)點(diǎn)的孩子必須是黑色結(jié)點(diǎn)。這一點(diǎn)的話，我們還有的補(bǔ)救，因?yàn)閮H僅影響本條路徑。

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 _color;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_color(RED) // 插入紅色結(jié)點(diǎn)，違反規(guī)則3，只影響一條路徑，甚至可能不影響。如果插入黑色結(jié)點(diǎn)，違反規(guī)則4，影響所有路徑{}
};

2. 父親的顏色

因?yàn)槲覀円迦氲慕Y(jié)點(diǎn)是紅色的，那么在我們插入的位置，它的父親要么是紅色的要么是黑色的。如果是黑色的，那么就是如下的情況

我們可以看到，似乎并未影響整棵樹(shù)的結(jié)構(gòu)，不違反任何一條規(guī)則。最短路徑仍然不超過(guò)最長(zhǎng)路徑的兩倍。每條路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)仍然相等。所以如果插入一個(gè)新節(jié)點(diǎn)以后，如果此處它的父親是黑色的，完美，不需要做出任何修改即可。如果父親甚至都不存在，那么這個(gè)結(jié)點(diǎn)就是這顆樹(shù)了。我們只需要將這個(gè)結(jié)點(diǎn)變?yōu)楹谏纯?。如果父親是紅色的話，那么就比較麻煩了。

如下圖所示，就是插入的時(shí)候父親為紅色，顯然已經(jīng)違反了規(guī)則3了，此時(shí)我們需要對(duì)這顆樹(shù)進(jìn)行處理了。

3. 叔叔的顏色為紅色

如果我們插入了一個(gè)結(jié)點(diǎn)以后，此時(shí)，父親結(jié)點(diǎn)為紅色，且有父親的兄弟，即叔叔，且叔叔的顏色是紅色。

即如下的情況，uncle存在且為紅

這樣的話，我們可以將parent和uncle都變黑，然后讓grandfather變紅，即如下的情形

這樣的話，在黑色結(jié)點(diǎn)數(shù)量不變的條件下，使得連續(xù)紅色結(jié)點(diǎn)的問(wèn)題暫時(shí)解決了?，F(xiàn)在原本cur為紅色的問(wèn)題轉(zhuǎn)換為了grandfather為紅色的問(wèn)題。

此時(shí)的話，如果這個(gè)grandfather如果沒(méi)有父親了，那么根據(jù)規(guī)則1，我們只需要讓他變?yōu)楹谏纯?。此時(shí)僅僅只是所有的路徑多了一個(gè)黑色結(jié)點(diǎn)。如果grandfather有父親，那么我們只需要讓grandfather變?yōu)閏ur，繼續(xù)向上處理即可

在這里繼續(xù)向上處理的時(shí)候又分為以下幾種情況

1. grandfather沒(méi)有父親，那么直接讓grandfather變黑即可
2. grandfather有父親，且父親為黑色，那么由于前面的樹(shù)本身就是滿足紅黑樹(shù)規(guī)則，這里改變了之后仍然滿足紅黑樹(shù)規(guī)則，那么不處理即可
3. grandfather有父親，且父親為紅色，這樣的情況下，父親為紅色，就隱含了必然存在grandfather的grandfather，因?yàn)樵瓉?lái)的樹(shù)也要滿足紅黑樹(shù)的規(guī)則，這樣一來(lái)就是類(lèi)似的問(wèn)題繼續(xù)往處理即可。

然后由于此時(shí)恰好uncle存在且為紅，那么我們只需要按照前面的邏輯進(jìn)行處理即可，即uncle和parent均變黑，然后grandfather變?yōu)榧t

然后又為了滿足根節(jié)點(diǎn)為紅，所以grandfather變?yōu)楹诩纯?/p>

4. 叔叔不存在

如下圖所示，當(dāng)叔叔不存在的時(shí)候，我們還插入了一個(gè)新節(jié)點(diǎn)以后，我們發(fā)現(xiàn)最長(zhǎng)路徑已經(jīng)超過(guò)了最短路徑的兩倍了。這時(shí)候單純的進(jìn)行變色，已經(jīng)無(wú)法解決問(wèn)題了。我們需要旋轉(zhuǎn)了。

所以我們就需要進(jìn)行旋轉(zhuǎn)＋變色了。

• 對(duì)于變色：與前面的情況類(lèi)似，即本來(lái)parent和uncle都為紅色的話，就把他們兩個(gè)變?yōu)楹谏?#xff0c;然后把grandfather變?yōu)榧t色就可以了。不過(guò)現(xiàn)在uncle不存在了。那我們就先不管它了，將parent變?yōu)楹谏?#xff0c;grandfather變?yōu)榧t色就可以了。
• 對(duì)于旋轉(zhuǎn)：這個(gè)就需要我們進(jìn)行具體的分析了，看看究竟是左旋還是右旋還是雙旋。具體判斷規(guī)則與AVL基本是一致的，如果是直線那么就是單旋，我們只需要分析誰(shuí)高就可以了。如果是折線就是雙旋，我們還是分析哪邊高就可以了。

如上圖所示的情形就是右單旋就可以了

5. 叔叔存在且為黑

我們接著前面的圖，我們繼續(xù)插入一個(gè)新的結(jié)點(diǎn)

那么此時(shí)的uncle存在且為紅，我們進(jìn)行相應(yīng)的處理后，變?yōu)槿缦碌那闆r

這時(shí)候，我們遇到了新的情況，uncle存在且為黑

那么此時(shí)的處理情形就和前面的uncle不存在是一樣的，直接旋轉(zhuǎn)加變色。這里的如何旋轉(zhuǎn)和變色統(tǒng)一結(jié)論后面詳細(xì)討論

總結(jié)

1. 紅黑樹(shù)的插入主要看uncle

2. uncle存在且為紅，變色+繼續(xù)往上更新

3. uncle不存在或uncle存在且為黑，旋轉(zhuǎn)+變色

6. 插入的抽象圖

• 如下是第一種情況，當(dāng)cur為紅，p為紅，g為黑,u存在且為紅的條件下。

在這種情況下，我們可以p和u改為黑色，g改為紅，然后把g當(dāng)成cur,繼續(xù)向上調(diào)整。

上面是我們的抽象圖，我們?nèi)绻唧w細(xì)化每一種情況的下是非常之麻煩的

比如說(shuō)當(dāng)a、b、c、d、e均為空，即cur是新增結(jié)點(diǎn)的時(shí)候，如下所示

當(dāng)a,b不為空，且cur是黑色結(jié)點(diǎn)。那么cde都是含有一個(gè)結(jié)點(diǎn)的子樹(shù)，那么cde的每個(gè)樣子都有四種情況，如下所示

由于它可以在a,b這兩個(gè)紅色結(jié)點(diǎn)任意處進(jìn)行插入，也就是說(shuō)，可以在四個(gè)位置插入。

那么這種變換的情況就復(fù)雜很多，有4*4*4*4共256種情況

如果cde有兩個(gè)黑節(jié)點(diǎn)的話，那么情況將更加復(fù)雜，畫(huà)圖已經(jīng)很難表示出來(lái)了

顯然我們?nèi)绻镁呦髨D的話，那么紅黑樹(shù)有無(wú)數(shù)種情況，所以我們只能使用抽象圖來(lái)表示這種情況。

所以根據(jù)前面的分析，我們就可以寫(xiě)出如下的代碼了。下面只是處理顏色的部分。

		//開(kāi)始處理顏色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){}}else{Node* uncle = grandfather->_left;if (uncle&& uncle->_color = RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){}}}

• 接下來(lái)，我們討論第二種情況，即cur為紅，p為紅，g為黑，u不存在/u存在且為黑

首先來(lái)分析uncle不存在的情況下，即如下的情況。此時(shí)我們可以注意到，由于uncle不存在，那么cur必然就是新插入的結(jié)點(diǎn)。此時(shí)我們就根據(jù)當(dāng)前的cur與p的關(guān)系來(lái)確定是單旋還是雙旋。旋轉(zhuǎn)之后，進(jìn)行變色。在這里的變色中，如果是單旋，就是g和p變色即可。如果是雙旋，那么就是cur和g變色

1. p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；相反p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)

   p、g變色—p變黑，g變紅

2. p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)，此時(shí)轉(zhuǎn)化了為了第一步的情況

再來(lái)看一下uncle存在且為黑的情況下。由于uncle存在且為黑，所以cur之前必然為黑色的，因?yàn)闉榱藵M足每條路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)相同，就代表著，cur必須為先前向上處理后的，在向上處理過(guò)程中，cur變?yōu)榱思t色。

當(dāng)uncle存在且為黑的情況下，他的變色以及旋轉(zhuǎn)規(guī)則都是與uncle不存在是一模一樣的

1. p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；相反p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)

   p、g變色—p變黑，g變紅

2. p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)，此時(shí)轉(zhuǎn)化了為了第一步的情況

所以最終插入的完整代碼為

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK; //根節(jié)點(diǎn)必須是黑色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{return false;}}cur = new Node(kv); //插入紅色結(jié)點(diǎn)if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;//開(kāi)始處理顏色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){if (parent->_left == cur){RotateR(grandfather);parent->_color = BLACK;grandfather->_color = RED;break;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;break;}}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){if (parent->_right == cur){RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;break;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;break;}}}}_root->_color = BLACK;return true;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;//改變parentparent->_right = curleft;parent->_parent = cur;//改變curleftif (curleft != nullptr){curleft->_parent = parent;}//改變curcur->_left = parent;cur->_parent = ppnode;//改變ppnodeif (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;//改變parentparent->_left = curright;parent->_parent = cur;//改變currightif (curright != nullptr){curright->_parent = parent;}//改變curcur->_right = parent;cur->_parent = ppnode;//改變ppnodeif (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}}

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

當(dāng)我們寫(xiě)完一個(gè)比較復(fù)雜的程序的時(shí)候，我們最好去寫(xiě)一個(gè)輔助代碼去驗(yàn)證它

1. 檢查平衡

如下代碼所示，可以去檢測(cè)我們實(shí)現(xiàn)的紅黑樹(shù)當(dāng)插入數(shù)據(jù)以后是否會(huì)出現(xiàn)不平衡的現(xiàn)象。檢查利用的就是每條路徑上黑色結(jié)點(diǎn)個(gè)數(shù)相同與不能出現(xiàn)連續(xù)的兩個(gè)紅色結(jié)點(diǎn)這兩條規(guī)則。

	bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr){return true;}if (root->_color == RED){return false;}int benchmark = 0;Node* cur = root;while (cur){if (cur->_color == BLACK){benchmark++;}cur = cur->_left;}return CheckColor(root, 0, benchmark);}bool CheckColor(Node* root, int blacknum, int benchmark){//檢查每條路徑的黑色結(jié)點(diǎn)數(shù)量是否相等if (root == nullptr){if (blacknum != benchmark){return false;}return true;}if (root->_color == BLACK){blacknum++;}//檢查顏色if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << ":" << "出現(xiàn)兩個(gè)連續(xù)的紅色結(jié)點(diǎn)" << endl;return false;}return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark);}

2. 計(jì)算高度與旋轉(zhuǎn)次數(shù)

高度的代碼很簡(jiǎn)單，如下所示

	int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr){return 0;}int leftheight = Height(root->_left);int rightheight = Height(root->_right);return leftheight > rightheight ? 1 + leftheight : 1 + rightheight;}

對(duì)于旋轉(zhuǎn)次數(shù)，我們可以直接設(shè)置一個(gè)變量專(zhuān)門(mén)計(jì)數(shù)。每旋轉(zhuǎn)一次這個(gè)值加一次

	int Getrotatecount(){return _rotatecount;}

3. 驗(yàn)證

int main()
{RBTree<int, int> rb;srand(time(0));for (int i = 0; i < 10000; i++){int tmp = rand();rb.Insert(make_pair(tmp, tmp));//rb.Insert(make_pair(i, i));//cout << rb.IsBalance() << endl;//cout << i << ":" << tmp << endl;}cout << "height:" << rb.Height() << endl;cout << "rotatecount:" << rb.Getrotatecount() << endl;cout << rb.IsBalance() << endl;return 0;
}

我們使用上面的隨機(jī)數(shù)來(lái)進(jìn)行測(cè)試

運(yùn)行結(jié)果如下所示

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

紅黑樹(shù)和AVL樹(shù)都是高效的平衡二叉樹(shù)，增刪改查的時(shí)間復(fù)雜度都是logN，紅黑樹(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ù)更多。

從源代碼中我們也可以看出來(lái)，其實(shí)map與set的底層都是紅黑樹(shù)，而且是kv結(jié)構(gòu)的紅黑樹(shù)