C++_數據結構_詳解紅黑樹

?? 歡迎大家來到小傘的大講堂??

🎈🎈養成好習慣，先贊后看哦~🎈🎈

所屬專欄：C++學習
小傘的主頁：xiaosan_blog

制作不易！點個贊吧！！謝謝喵！！！

大家應該都學過平衡二叉樹(AVLTree)，了解到AVL樹的性質，其實平衡二叉樹最大的作用就是查找,AVL樹的查找、插入和刪除在平均和最壞情況下都是O(logn)。AVL樹的效率就是高在這個地方。如果在AVL樹中插入或刪除節點后，使得高度之差大于1。此時，AVL樹的平衡狀態就被破壞，它就不再是一棵二叉樹；為了讓它重新維持在一個平衡狀態，就需要對其進行旋轉處理, 那么創建一顆平衡二叉樹的成本其實不小. 這個時候就有人開始思考，并且提出了紅黑樹的理論，紅黑樹在業界應用很廣泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于紅黑樹結構實現的。那么紅黑樹到底比AVL樹好在哪里？C++_數據結構_AVL樹-CSDN博客

1.紅黑樹的概念

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

思考：為什么需要紅黑樹？?

對于二叉搜索樹，如果插入的數據是隨機的，那么它就是接近平衡的二叉樹，平衡的二叉樹，它的操作效率（查詢，插入，刪除）效率較高，時間復雜度是O（logN）。但是可能會出現一種極端的情況，那就是插入的數據是有序的（遞增或者遞減），那么所有的節點都會在根節點的右側或左側，此時，二叉搜索樹就變為了一個鏈表，它的操作效率就降低了，時間復雜度為O(N)，所以可以認為二叉搜索樹的時間復雜度介于O（logN）和O(N)之間，視情況而定。那么為了應對這種極端情況，紅黑樹就出現了，它是具備了某些特性的二叉搜索樹，能解決非平衡樹問題，紅黑樹是一種接近平衡的二叉樹（說它是接近平衡因為它并沒有像AVL樹的平衡因子的概念，它只是靠著滿足紅黑節點的5條性質來維持一種接近平衡的結構，進而提升整體的性能，并沒有嚴格的卡定某個平衡因子來維持絕對平衡）。

1.1 紅黑樹的規則

1.每個結點不是紅色就是黑色

2.根結點是黑色的

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

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

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

例：?

1.2 思考一下？紅黑樹如何確保最長路徑不超過最短路徑的兩倍的

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

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

最長路徑：由規則2和規則3可知：任何路徑不會含有連續的紅色節點，那么在最極端的場景下，最長路徑會出現在紅黑色節點交替，最長路徑的長度為2*bh。

2.根結點是黑色的

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

總結：?

對于紅黑樹的4點規則而言，理論上全黑最長路徑與一黑一紅最短路徑并不會每棵紅黑樹都存在，假設任意一條從根到NULL結點路徑的長度為x，那么bh <= h <= 2*bh。

1.3 紅黑樹的效率

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

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

2.紅黑樹的實現

2.1 紅黑樹的結構

#pragma once
//枚舉值表示顏色
enum Colour
{RED,BLACK
};//默認按key/val結構實現
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)//, _col(RED)，這里可以不用初始化，在后續插入時會給出相應措施//如果要想初始化的話，默認初始為RED，因為后續插入的if影響不大//思考是否可以初始化為黑色呢<————————————{}};template<class K, class V>
class RBTree{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
}

如果我們想要初始化顏色，為什么要默認是紅色呢？?

我們來分析一下如果我們插入一個新結點給的是黑色，那它一定會違反上面提到的紅黑樹的第5條性質——每條路徑上黑色結點的數量一致。?

因為原來每條路徑黑色結點數量是相同的，現在新插入一個黑色結點的話，那插入的這條路徑會增加一個黑色結點，但是其它路徑數量不變，所以其它所有的路徑黑色結點數量都和這一條不相等，這樣就比較麻煩了。
那如果我們插入結點默認給紅色呢？會違反規則嗎？
那紅色的話其實要看具體情況了：
如果插入一個紅色結點，但是它的父親也是紅色，那就出事了，因為紅黑樹里面不能出現連續的紅色結點，那這種情況就需要調整了。
但如果它的父親是黑色，那就沒問題，不需要進行什么處理。

所以我們新插入的結點給成紅色，當然如果是第一次插入根結點我們可以直接給黑色，因為紅黑樹要求根結點必須是黑色的。?

2.2 紅黑樹的插入

1.找到插入位置：我們遍歷紅黑樹，找到新節點應該插入的位置。這通常是通過比較新節點的鍵與當前節點的鍵來完成的，直到找到一個空位置（即葉子節點的子節點位置）為止。在這個過程中，我們還記錄了新節點的父節點，以便后續操作。

2.插入新節點：一旦找到插入位置，我們將新節點插入到樹中。這涉及到將新節點的父節點指針指向之前記錄的父節點，并根據新節點的鍵值更新父節點的左子節點或右子節點指針。

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;//與AVL樹一樣，左小右大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;
}

3.修復紅黑樹性質：插入新節點后，紅黑樹可能不再滿足其性質。因此，我們需要進行一系列操作來修復這些性質。這主要包括檢查新節點的父節點和叔叔節點的顏色，并根據需要執行旋轉和重新著色操作。?

2.2.1 紅黑樹的插入過程

插入一個值按二叉搜索樹規則進行插入，插入后我們只需要觀察是否符合紅黑樹的4條規則。

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

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

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

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

——————————————————————————————————————————?

2.2.2 情況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.2.3 情況2：單旋+變??

c為紅，p為紅，g為黑，u不存在或者u存在且為黑，u不存在，則c一定是新增結點，u存在且為黑，則c一定不是新增，c之前是黑色的，是在c的?樹中插?，符合情況1，變?將c從黑色變成紅色，更新上來的。
分析：p必須變黑，才能解決，連續紅色結點的問題，u不存在或者是黑色的，這?單純的變色?法解決問題，需要旋轉 + 變色。
? ? ? ? ?g
? ? p ? ? ? ? u
c ?

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

2.2.4 情況3：雙旋+變色

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

分析：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的父親是黑色還是紅色或者空都不違反規則

2.3?紅黑樹插入實現?

左單旋：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}

?右單旋：

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 (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}
}

紅黑樹插入?

// 旋轉代碼的實現跟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;//與AVL樹一樣，左小右大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;if (parent == grandfather->_left){//   g// p   uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//如果g的?親還是紅?，那么就還需要繼續處理；如果g的?親是??，則處理結束//了；如果g就是整棵樹的根，再把g變回??// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解//決問題，需要旋轉 + 變?//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p    u//     c//p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解//決問題，需要旋轉 + 變?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{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

回答前面問題：有規則可知，對于空樹，父親節點必須為黑色節點，當if語句將其排除，那么對于非空樹，插入則必須為紅色節點。所以如果將顏色是否初始化為RED，并不影響其插入。
if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根節點必須為黑色節點return true;}

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

2.5?紅?樹的驗證

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

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

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

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

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

我們也要檢測其是否滿足紅黑樹的性質，我們需要兩個函數：?

a. Check 函數
Check 函數用于遞歸地檢查紅黑樹的性質是否得到滿足。它接受三個參數：當前節點 cur、從根節點到當前節點路徑上的黑色節點數 blackNum 和從根節點到最左側路徑上的黑色節點數 refBlackNum。

空節點檢查：如果當前節點為空（cur == nullptr），則檢查從根節點到該路徑的黑色節點數 blackNum 是否與最左側路徑的黑色節點數 refBlackNum 相等。如果不相等，則輸出錯誤信息并返回 false。
連續紅色節點檢查：如果當前節點為紅色且其父節點也為紅色，則違反了紅黑樹的性質（性質 4），輸出錯誤信息并返回 false。
黑色節點計數：如果當前節點為黑色，則增加 blackNum 的計數。
遞歸檢查子節點：遞歸調用 Check 函數檢查當前節點的左子樹和右子樹，只有當左右子樹都返回 true 時，當前節點才返回 true。

b. IsBalance 函數
IsBalance 函數用于檢查整棵紅黑樹是否平衡。

根節點顏色檢查：如果根節點存在且為紅色，則直接返回 false，因為根節點必須是黑色（性質 2）。
計算最左側路徑黑色節點數：從根節點開始，沿著最左側路徑遍歷樹，計算遇到的黑色節點數，存儲在 refBlackNum 中。
調用 Check 函數：從根節點開始，調用 Check 函數遞歸地檢查整棵樹是否滿足紅黑樹的性質。傳遞的初始黑色節點數 blackNum 為 0，參考黑色節點數 refBlackNum 為之前計算得到的值。

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

3. 紅黑樹的刪除

紅黑樹的刪除呢我們這里不做詳細講解：紅黑樹的刪除比較復雜，要比插入還復雜好多。
但關鍵的是紅黑樹的刪除在考研包括我們找工作筆試面試的時候一般是不會考察的，所以我們也沒必要去學。
大家有興趣的可以自己查找相關資料進行學習，可以參考《算法導論》或者《STL源碼剖析》

4.?紅黑樹與AVL樹的比較

紅黑樹和AVL樹都是高效的自平衡搜索二叉樹，增刪改查的時間復雜度都是O(l o g 2 N log_2 Nlog2N)。
紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，所以AVL樹的插入和刪除操作比紅黑樹更耗時。
因為AVL樹在插入和刪除節點后，會進行更多的旋轉操作以維持一個較為嚴格的平衡，所以插入和刪除操作的時間復雜度更高。
相對而言，紅黑樹對平衡的控制比較寬松，降低了插入刪除時需要旋轉的次數，所以在經常進行增刪的結構中性能比AVL樹更優，而且紅黑樹實現比較簡單，所以實際運用中紅黑樹更多。
在實際應用中，紅黑樹的使用更廣泛。許多編程語言和庫都使用紅黑樹作為基礎數據結構，例如C++ STL中的std::map和std::set就是基于紅黑樹實現的。

5. 源碼分享

5.1 含有迭代器版本

RBTreeNode.h

#pragma onceenum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{// 這里更新控制平衡也要加入parent指針T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Self operator++(){if (_node->_right){// 右不為空，中序下一個訪問的節點是右子樹的最左(最小)節點Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else{// 右為空，祖先里面孩子是父親左的那個祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator--(){if (_node == nullptr)  // --end(){// --end()，特殊處理，走到中序最后一個結點，整棵樹的最右結點Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 左子樹不為空，中序左子樹最后一個Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩子是父親右的那個祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s) const{return _node != s._node;}bool operator== (const Self& s) const{return _node == s._node;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true };}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return { Iterator(cur, _root), false };}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}// 鏈接父親cur->_parent = parent;// 父親是紅色，出現連續的紅色節點，需要處理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//   g// p   uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p    u//     cRotateL(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{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return { Iterator(newnode, _root), 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 (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}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* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}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;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private:int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};

test.cpp

//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include<iostream>
//#include<vector>
//#include<time.h>
//using namespace std;
//
//#include"RBTreeNode.h"
//
//void TestTree2()
//{
//const int N = 10000000;
//vector<int> v;
//v.reserve(N);
//srand(time(0));
//for (size_t i = 0; i < N; i++)
//{
//	v.push_back(rand() + i);
//}
//size_t begin2 = clock();
//AVLTree<int, int> t;
//for (auto e : v)
//{
//	t.Insert(make_pair(e, e));
//}
//	size_t end2 = clock();
//
//	size_t begin22 = clock();
//	RBTree<int, int> rbt;
//	for (auto e : v)
//	{
//		rbt.Insert(make_pair(e, e));
//	}
//	size_t end22 = clock();
//
//	cout << "AVL Insert:" << end2 - begin2 << endl;
//	cout << "RB Insert:" << end22 - begin22 << endl;
//
//	cout <<"AVL IsBalance:"<< t.IsBalanceTree() << endl;
//	cout << "RB IsBalance:" << rbt.IsBalance() << endl;
//
//
//	cout << "AVL Height:" << t.Height() << endl;
//	cout << "AVL Size:" << t.Size() << endl;
//
//	cout << "RB Height:" << rbt.Height() << endl;
//	cout << "RB Size:" << rbt.Size() << endl;
//
//	size_t begin1 = clock();
//	// 確定在的值
//	for (auto e : v)
//	{
//		t.Find(e);
//	}
//	// 隨機值
//	/*for (size_t i = 0; i < N; i++)
//	{
//		t.Find((rand() + i));
//	}*/
//	size_t end1 = clock();
//	cout << "AVL Find:" << end1 - begin1 << endl;
//
//	size_t begin11 = clock();
//	// 確定在的值
//	for (auto e : v)
//	{
//		rbt.Find(e);
//	}
//	// 隨機值
//	/*for (size_t i = 0; i < N; i++)
//	{
//		t.Find((rand() + i));
//	}*/
//	size_t end11 = clock();
//	cout << "RB Find:" << end11 - begin11 << endl;
//}
//
//int main()
//{
//	TestTree2();
//
//	return 0;
//}

5.2?不含有迭代器版本

RBTreeNode.h

#pragma onceenum Colour
{RED,BLACK
};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: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;//與AVL樹一樣，左小右大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;if (parent == grandfather->_left){//   g// p   uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//如果g的?親還是紅?，那么就還需要繼續處理；如果g的?親是??，則處理結束//了；如果g就是整棵樹的根，再把g變回??// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解//決問題，需要旋轉 + 變?//     g//   p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p    u//     c//p必須變?，才能解決，連續紅?結點的問題，u不存在或者是??的，這?單純的變??法解//決問題，需要旋轉 + 變?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{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}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 (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}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* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}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;}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: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);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"RBTreeNode.h"void TestRBTree1()
{RBTree<int, int> t;// 常規的測試用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的帶有雙旋場景的測試用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalance() << endl;
}int main()
{TestRBTree1();return 0;
}