數據結構進階詳談紅黑樹

1. 紅?樹的概念

紅?樹的規則

紅?樹如何確保最?路徑不超過最短路徑的2倍的？

紅?樹的效率：

2. 紅?樹的實現

紅?樹的結構

紅?樹的插?

紅?樹樹插??個值的?概過程

情況1：變?

情況2：單旋+變?

情況3：雙旋+變?

3. 紅?樹的插?代碼實現

4. 紅?樹的查找

5. 紅?樹的驗證

6. 結語

1. 紅?樹的概念

紅?樹是?棵?叉搜索樹，他的每個結點增加?個存儲位來表?結點的顏?，可以是紅?或者??。通過對任何?條從根到葉?的路徑上各個結點的顏?進?約束，紅?樹確保沒有?條路徑會?其他路徑?出2倍，因?是接近平衡的。

紅?樹的規則

1. 每個結點不是紅?就是??

2. 根結點是??的

3. 如果?個結點是紅?的，則它的兩個孩?結點必須是??的，也就是說任意?條路徑不會有連續的紅?結點。

4. 對于任意?個結點，從該結點到其所有NULL結點的簡單路徑上，均包含相同數量的??結點

說明：《算法導論》等書籍上補充了?條每個葉?結點(NIL)都是??的規則。他這?所指的葉?結點不是傳統的意義上的葉?結點，?是我們說的空結點，有些書籍上也把NIL叫做外部結點。NIL是為了?便準確的標識出所有路徑，《算法導論》在后續講解實現的細節中也忽略了NIL結點，所以我們知道?下這個概念即可。

紅?樹如何確保最?路徑不超過最短路徑的2倍的？

由規則4可知，從根到NULL結點的每條路徑都有相同數量的??結點，所以極端場景下，最短路徑就就是全是??結點的路徑，假設最短路徑?度為bh(black height)。

由規則2和規則3可知，任意?條路徑不會有連續的紅?結點，所以極端場景下，最?的路徑就是???紅間隔組成，那么最?路徑的?度為2*bh。

綜合紅?樹的4點規則??，理論上的全?最短路徑和???紅的最?路徑并不是在每棵紅?樹都存在的。假設任意?條從根到NULL結點路徑的?度為x，那么bh <= h <= 2*bh。

紅?樹的效率：

假設N是紅?樹樹中結點數量，h最短路徑的?度，那么 h ? 1 <= N < 2 ^2?h ? 1, 由此推出h ≈ logN ，也就是意味著紅?樹增刪查改最壞也就是?最?路徑2 ? logN，那么時間復雜度還O(logN)

紅?樹的表達相對AVL樹要抽象?些，AVL樹通過?度差直觀的控制了平衡。紅?樹通過4條規則的顏?約束，間接的實現了近似平衡，他們效率都是同?檔次，但是相對??，插?相同數量的結點，紅?樹的旋轉次數是更少的，因為他對平衡的控制沒那么嚴格。

2. 紅?樹的實現

紅?樹的結構

// 枚舉值表?顏?
enum Colour
{RED,BLACK
};
// 這?我們默認按key/value結構實現
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;
};

紅?樹的插?

紅?樹樹插??個值的?概過程

1. 插??個值按?叉搜索樹規則進?插?，插?后我們只需要觀察是否符合紅?樹的4條規則。

2. 如果是空樹插?，新增結點是??結點。如果是?空樹插?，新增結點必須紅?結點，因為?空樹插?，新增??結點就破壞了規則4，規則4是很難維護的。

3. ?空樹插?后，新增結點必須紅?結點，如果?親結點是??的，則沒有違反任何規則，插?結束

4. ?空樹插?后，新增結點必須紅?結點，如果?親結點是紅?的，則違反規則3。進?步分析，c是紅?，p為紅，g必為?，這三個顏?都固定了，關鍵的變化看u的情況，需要根據u分為以下?種情況分別處理。

說明：下圖中假設我們把新增結點標識為c (cur)，c的?親標識為p(parent)，p的?親標識為g(grandfather)，p的兄弟標識為u（uncle）

情況1：變?

c為紅，p為紅，g為?，u存在且為紅，則將p和u變?，g變紅。在把g當做新的c，繼續往上更新。

分析：因為p和u都是紅?，g是??，把p和u變?，左邊?樹路徑各增加?個??結點，g再變紅，相當于保持g所在?樹的??結點的數量不變，同時解決了c和p連續紅?結點的問題，需要繼續往上更新是因為，g是紅?，如果g的?親還是紅?，那么就還需要繼續處理；如果g的?親是??，則處理結束了；如果g就是整棵樹的根，再把g變回??。

情況1只變?，不旋轉。所以?論c是p的左還是右，p是g的左還是右，都是上?的變?處理?式。

跟AVL樹類似，圖0我們展?了?種具體情況，但是實際中需要這樣處理的有很多種情況。

圖1將以上類似的處理進?了抽象表達，d/e/f代表每條路徑擁有hb個??結點的?樹，a/b代表每條路徑擁有hb-1個??結點的根為紅的?樹，hb>=0。

圖2/圖3/圖4，分別展?了hb == 0/hb == 1/hb == 2的具體情況組合分析，當hb等于2時，這?組合情況上百億種，這些樣例是幫助我們理解，不論情況多少種，多么復雜，處理?式?樣的，變?再繼續往上處理即可，所以我們只需要看抽象圖即可

情況2：單旋+變?

c為紅，p為紅，g為?，u不存在或者u存在且為?，u不存在，則c?定是新增結點，u存在且為?，則c?定不是新增，c之前是??的，是在c的?樹中插?，符合情況1，變?將c從??變成紅?，更新上來的。

分析：p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解決問題，需要旋轉+變?。

? ? ? ? ? g

? ? p? ? ? ? u

如果p是g的左，c是p的左，那么以g為旋轉點進?右單旋，再把p變?，g變紅即可。p變成課這顆樹新的根，這樣?樹??結點的數量不變，沒有連續的紅?結點了，且不需要往上更新，因為p的?親是??還是紅?或者空都不違反規則。

? ? ? ? g

? ? u? ? ? p

? ? ? ? ? ? ? ?c

如果p是g的右，c是p的右，那么以g為旋轉點進?左單旋，再把p變?，g變紅即可。p變成課這顆樹新的根，這樣?樹??結點的數量不變，沒有連續的紅?結點了，且不需要往上更新，因為p的?親是??還是紅?或者空都不違反規則。

情況3：雙旋+變?

分析：p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解決問題，需要旋轉+變?。

? ? ? ? ? g

? ? p? ? ? ? ?u

? ? ? c

如果p是g的左，c是p的右，那么先以p為旋轉點進?左單旋，再以g為旋轉點進?右單旋，再把c變 ?，g變紅即可。c變成課這顆樹新的根，這樣?樹??結點的數量不變，沒有連續的紅?結點了，且不需要往上更新，因為c的?親是??還是紅?或者空都不違反規則。

? ? ? ? g

? ? u? ? ? ?p

? ? ? ?c

如果p是g的右，c是p的左，那么先以p為旋轉點進?右單旋，再以g為旋轉點進?左單旋，再把c變 ?，g變紅即可。c變成課這顆樹新的根，這樣?樹??結點的數量不變，沒有連續的紅?結點了，且不需要往上更新，因為c的?親是??還是紅?或者空都不違反規則。

3. 紅?樹的插?代碼實現

// 旋轉代碼的實現跟AVL樹是?樣的，只是不需要更新平衡因?
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);// 新增結點。顏?紅?給紅?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* grandfather = parent->_parent;// g// p uif (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// u存在且為紅 -》變?再繼續往上處理parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// u存在且為?或不存在 -》旋轉+變?if (cur == parent->_left){// g// p u//c//單旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//雙旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且為紅，-》變?即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且為?{// 情況?：叔叔不存在或者存在且為?// 旋轉+變?// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

4. 紅?樹的查找

按?叉搜索樹邏輯實現即可，搜索效率為 O(logN)

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

5. 紅?樹的驗證

這?獲取最?路徑和最短路徑，檢查最?路徑不超過最短路徑的2倍是不可?的，因為就算滿?這個條件，紅?樹也可能顏?不滿?規則，當前暫時沒出問題，后續繼續插?還是會出問題的。所以我們還是去檢查4點規則，滿?這4點規則，?定能保證最?路徑不超過最短路徑的2倍。

1. 規則1枚舉顏?類型，天然實現保證了顏?不是??就是紅?。

2. 規則2直接檢查根即可

3. 規則3前序遍歷檢查，遇到紅?結點查孩?不太?便，因為孩?有兩個，且不?定存在，反過來檢查?親的顏?就?便多了。

4. 規則4前序遍歷，遍歷過程中?形參記錄跟到當前結點的blackNum(??結點數量)，前序遍歷遇到??結點就++blackNum，?到空就計算出了?條路徑的??結點數量。再任意?條路徑??結點數量作為參考值，依次?較即可。

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){// 前序遍歷?到空時，意味著?條路徑?完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在??結點的數量不相等的路徑" << endl;return false;}return true;}// 檢查孩?不太?便，因為孩?有兩個，且不?定存在，反過來檢查?親就?便多了if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在連續的紅?結點" << 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);
}