前言

相信很多人初學者聽到了紅黑樹后心中不免有些心慌，那你看到了這篇文章后相信會有所收獲，我其實剛開始也是對紅黑樹抱著一種害怕甚至是恐懼，但是在老師的幫助下也終于慢慢的不在恐懼了，你想知道為什么的話就繼續(xù)往下看吧。（注意本篇博客只講解了紅黑樹的插入，沒有講解紅黑樹的刪除，刪除比插入還要難一些，為了更好的閱讀體驗，就不再講解了）

---

1 紅黑樹的概念

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

如果說AVL樹是大佬設計的話，那么紅黑樹就是大佬中的大佬設計出來的，為什么這么說呢，我們接下來慢慢看。

---

2 紅黑樹的性質

• 每個結點不是紅色就是黑色
• 根節(jié)點是黑色的
• 如果一個節(jié)點是紅色的，則它的兩個孩子結點是黑色的
• 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上均包含相同數目的黑色結點
• 每個葉子結點都是黑色的 (此處的葉子結點指的是空結點)

我們先不要看最后一條性質，其他性質中比較重要的就是性質三和性質四，我們可以用自己的話來解讀性質三和性質四：
性質三的意思是沒有連續(xù)紅色結點
性質四的意思是每條路徑下的黑色結點數量是相等的

大家思考一下，為什么滿足了上面性質就能夠保證紅黑樹中最長路徑中節(jié)點個數不會超過最短路徑節(jié)點個數的兩倍？

我們可以從極限的條件下來判斷：
最短路徑是全黑，最長路徑是紅黑相間，由于要滿足性質三和性質四所以最長路徑除以最短路徑最大也不會超過二倍。

我們再來看看最后一個性質，有些教科書上可能會有NIL結點的定義，并且把顏色定義為黑色，注意這里的NIL結點并不是一個真正有效的節(jié)點，而是一個空結點。通過每條空結點來標識每一條路徑，如在上圖中就存在著11條路徑。

通過紅黑樹的性質我們也不難發(fā)現，其實紅黑樹的平衡并沒有AVL樹那么嚴格，因為紅黑樹只需要保證最長路徑的結點個數不會超過最短路徑節(jié)點個數兩倍即可，但是AVL樹要求著所有子樹高度差絕對值不超過1。這就導致了紅黑樹的旋轉條件是比AVL樹更加苛刻的，也就是在同等條件下紅黑樹旋轉次數是有較大機率低于AVL樹的，那么紅黑樹的性能肯定是比AVL要好上一些的（旋轉是有代價的)，如果還沒有了解過旋轉，建議先看看博主的上一篇博客:
[AVL樹的旋轉]

---

3 紅黑樹的模擬實現

3.1 節(jié)點的定義

這個很簡單，我們已經講解過很多次了：

#pragma onceenum Corlor {RED,BLACK };template<class K, class V> struct RBTreeNode {RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Corlor _corlor;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _corlor(RED){} };template<class K, class V> class RBTree {typedef RBTreeNode<K, V> Node; private:Node* _root = nullptr; };

這里問題就來了，新節(jié)點給的顏色是給紅色還是給黑色呢？
給紅色的話就可能違背性質三，給黑色結點就違背性質四。如果是你你想違背哪個性質？
這里給新節(jié)點的默認顏色為紅色比較好，為什么呢？
給出紅色結點的話，我們可能就只需要調整本路徑下結點顏色，但是給黑色結點的話其他路徑黑色結點就不相等了，調整的代價肯定更大。所以新節(jié)點的默認顏色給紅色是比較合理的。

我們觀察上圖，如果我們在11 或者15 下插入新節(jié)點，那么這就太好了，不需要進一步調整，插入后還是一顆紅黑樹，但是我們想要在6 22 27下面插入新節(jié)點的話，就要調整了，具體怎樣調整我們下面會詳細講解。

3.2 分類

約定:cur為當前節(jié)點，p為父節(jié)點，g為祖父節(jié)點，u為叔叔節(jié)點
紅黑樹調整分類的關鍵就是看叔叔。

3.2.1 情況一

cur為紅，p為紅，g為黑，u存在且為紅

老規(guī)矩，我們這里畫的仍然是抽象圖，表示無數種情況，但是他們都可以用同一種方法來解決。
此時我們只需要將p和u置黑，將g置紅，然后接著往上調整。
為什么要繼續(xù)往上調整呢？通過觀察我們可以很容易分析出問題所在，這樣一次調整了后各個路徑上黑色結點數目并沒有發(fā)生改變，但是有可能g結點的父親結點是紅色的，而導致又出現了連續(xù)紅色結點（注意，調整了后有可能再次調整使用的方法不在是第一種情況）
繼續(xù)向上調整的話，直到不滿足連續(xù)紅色結點或者已經調整到了根節(jié)點。

3.2.2 情況二

cur為紅，p為紅，g為黑，u不存在/u存在且為黑

我們先分析第一種情況：u不存在。
如果u不存在的話，那么cur一定是新增。此時光變色已經無法解決問題了，因為此時已經不滿足最長路徑中節(jié)點個數不會超過最短路徑節(jié)點個數的兩倍，就需要旋轉處理：
這里處理方式是：右單旋+p變黑，g變紅。
也有可能p和cur都在右邊且在一條直線上，所以處理方式可能是：左單旋+p變黑，g變紅。
總結本次調整方法為：單旋+p變黑，g變紅。

同理，當u存在且為黑的時候仍然是同種處理方式：
旋轉變色完以后就不用再向上更新了。

3.2.3 情況三

cur為紅，p為紅，g為黑，u不存在/u存在且為黑

等等，這種方式不就是第二種方式嗎？
別著急，我們先來看看圖：

從圖片中我們不難發(fā)現，g p cur 三者并沒有在一條直線，而是一種折線關系，這種情況我們只是單旋就處理不了了，在這張圖中我們先以p點進行左單旋，在以g點進行右單旋上。
（注意，我們在b和c下面插入結點導致引起上面這種關系的都可以用這種方式處理）

當然，不只是這一種情況，還可能是反著來，那么處理方式就可能是：
以p右單旋+以g左單旋+cur變黑，g變紅。
所以這次情況處理方式是：雙旋+cur變黑，g變紅
旋轉變色完以后就不用再向上更新了。

3.3 代碼實現

bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_corlor = BLACK;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);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent && parent->_corlor == RED){Node* grand = parent->_parent;assert(grand);assert(grand->_corlor == BLACK);if (grand->_left == parent){Node* uncle = grand->_right;//情況一：uncle存在且為紅if (uncle && uncle->_corlor == RED){uncle->_corlor = parent->_corlor = BLACK;grand->_corlor = RED;//繼續(xù)往上處理cur = grand;parent = cur->_parent;}else{//情況二和三：//1 :parent->_left==cur（右單旋+變色）// g// p u//cif (parent->_left == cur){RotateR(grand);parent->_corlor = BLACK;grand->_corlor = RED;}else{//2 :parent->_right==cur（左單旋+右單旋+變色）// g// p u// cRotateL(parent);RotateR(grand);cur->_corlor = BLACK;grand->_corlor = RED;}//此時已經旋轉變色完成，可以break出去break;}}else//grand->_right=parent{Node* uncle = grand->_left;//情況一：uncle存在且為紅if (uncle && uncle->_corlor == RED){uncle->_corlor = parent->_corlor = BLACK;grand->_corlor = RED;//繼續(xù)往上處理cur = grand;parent = cur->_parent;}else{//情況二和三：//1 :parent->_right==cur（左單旋+變色）// g// u p// cif (parent->_right == cur){RotateL(grand);parent->_corlor = BLACK;grand->_corlor = RED;}else{//2 :parent->_left==cur（右單旋+左單旋+變色）// g// u p// cRotateR(parent);RotateL(grand);cur->_corlor = BLACK;grand->_corlor = RED;}//此時已經旋轉變色完成，可以break出去break;}}}_root->_corlor = BLACK;return true;}

3.4 紅黑樹的驗證

驗證的話我們要從紅黑樹的性質開始著手，只要滿足了紅黑樹的幾個性質自然就沒啥問題.

最主要的驗證是性質三和性質四：

//bool prevCheck(Node* root, int blackCnt, int& benchmark)bool prevCheck(Node* root, int blackCnt, int benchmark){if (root == nullptr){/*if (benchmark == 0){benchmark=blackCnt;return true;}*/if (benchmark != blackCnt){cout << "每條路徑上的黑色結點不相等" << endl;return false;}else{return true;}}if (root->_corlor == BLACK){++blackCnt;}if (root->_corlor == RED && root->_parent->_corlor == RED){cout << "有連續(xù)的紅色結點" << endl;return false;}return prevCheck(root->_left, blackCnt, benchmark)&& prevCheck(root->_right, blackCnt, benchmark);}bool isbalance(){if (_root && _root->_corlor == RED){cout << "根節(jié)點不是黑色" << endl;return false;}int benchMark = 0;Node* cur = _root;while (cur){if (cur->_corlor == BLACK)++benchMark;cur = cur->_left;}int blackCnt = 0;return prevCheck(_root, blackCnt, benchMark);}

處理方式有很多種，像每條路徑下的黑色節(jié)點我們可以一次性先算出來然后傳參數即可，也可以不算出來，傳參數引用來修改。具體方式大家可以自行選擇。
大家測試時最好多用幾組隨機數測測。

---

5 總結

大家看到了這里相信也對紅黑樹有了一個譜，其實說難吧，感覺還沒有剛學AVL的旋轉難，關鍵是如何把圖畫好，跟著圖一步一步的來，大概率是不會出錯的。如果該文對你有幫助的話能不能一鍵三聯支持博主呢

總結

以上是生活随笔為你收集整理的【手撕红黑树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。