一、紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍（即最長路徑不超過最短路徑的兩倍，近似平衡），因而是接近平衡的。

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

1. 每個結(jié)點不是紅色就是黑色
2. 根節(jié)點是黑色的
3. 如果一個節(jié)點是紅色的，則它的兩個孩子結(jié)點必須是黑色的（即任何路徑?jīng)]有連續(xù)的紅色結(jié)點）
4. 對于每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點（每條路徑上的黑色結(jié)點個數(shù)相同，這里的路徑包括空結(jié)點）
5. 每個葉子結(jié)點都是黑色的(此處的葉子結(jié)點指的是空結(jié)點，已經(jīng)不在是傳統(tǒng)的葉子結(jié)點了，圖中的NIL結(jié)點就是空結(jié)點）

這里對第四點做一補充說明

對于下面這棵樹有11條路徑，而不是5條路徑，因為空結(jié)點也包括在內(nèi)

如果不清楚上面的這一點，如果遇到下面這棵樹，可能會誤以為他是紅黑樹，實際上它不是紅黑樹。

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

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

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

如下圖所示， 最長路徑就是黑紅相間的情況，最短路徑就是全黑的情況。其他路徑都是在這兩者之間的，此時我們也不難看出最長路徑不超過最短路徑的兩倍。如果最短路徑為N，那么最長路徑就是2N-1，因為根節(jié)點一定是黑色的，最終的葉子結(jié)點也一定是黑色的。

三、紅黑樹和AVL樹對比

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

	AVL樹	紅黑樹
高度對比	高度差不超過一	最長路徑不超過最短路徑的兩倍
插入1000個值	logN---->10	2*logN---->20
插入10億個值	logN---->30	2*logN---->60

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

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

四、紅黑樹的插入

1. 紅黑樹的結(jié)點定義

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

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

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é)點，違反規(guī)則3，只影響一條路徑，甚至可能不影響。如果插入黑色結(jié)點，違反規(guī)則4，影響所有路徑{}
};

2. 父親的顏色

因為我們要插入的結(jié)點是紅色的，那么在我們插入的位置，它的父親要么是紅色的要么是黑色的。如果是黑色的，那么就是如下的情況

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

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

3. 叔叔的顏色為紅色

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

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

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

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

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

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

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

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

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

4. 叔叔不存在

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

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

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

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

5. 叔叔存在且為黑

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

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

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

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

總結(jié)

1. 紅黑樹的插入主要看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ì)化每一種情況的下是非常之麻煩的

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

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

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

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

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

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

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

		//開始處理顏色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){}}}

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

首先來分析uncle不存在的情況下，即如下的情況。此時我們可以注意到，由于uncle不存在，那么cur必然就是新插入的結(jié)點。此時我們就根據(jù)當(dāng)前的cur與p的關(guān)系來確定是單旋還是雙旋。旋轉(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的右孩子，則針對p做左單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的左孩子，則針對p做右單旋轉(zhuǎn)，此時轉(zhuǎn)化了為了第一步的情況

再來看一下uncle存在且為黑的情況下。由于uncle存在且為黑，所以cur之前必然為黑色的，因為為了滿足每條路徑上的黑色結(jié)點個數(shù)相同，就代表著，cur必須為先前向上處理后的，在向上處理過程中，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的右孩子，則針對p做左單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的左孩子，則針對p做右單旋轉(zhuǎn)，此時轉(zhuǎn)化了為了第一步的情況

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

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK; //根節(jié)點必須是黑色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é)點if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;//開始處理顏色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;}}}

五、紅黑樹的驗證

當(dāng)我們寫完一個比較復(fù)雜的程序的時候，我們最好去寫一個輔助代碼去驗證它

1. 檢查平衡

如下代碼所示，可以去檢測我們實現(xiàn)的紅黑樹當(dāng)插入數(shù)據(jù)以后是否會出現(xiàn)不平衡的現(xiàn)象。檢查利用的就是每條路徑上黑色結(jié)點個數(shù)相同與不能出現(xiàn)連續(xù)的兩個紅色結(jié)點這兩條規(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é)點數(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)兩個連續(xù)的紅色結(jié)點" << endl;return false;}return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark);}

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

高度的代碼很簡單，如下所示

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

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

	int Getrotatecount(){return _rotatecount;}

3. 驗證

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

我們使用上面的隨機數(shù)來進(jìn)行測試

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

六、 紅黑樹與AVL樹的比較

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

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