C++《紅黑樹》

在之前的篇章當中我們已經了解了基于二叉搜索樹的AVL樹，那么接下來在本篇當中將繼續來學習另一種基于二叉搜索樹的樹狀結構——紅黑樹，在此和之前學習AVL樹類似還是通過先了解紅黑樹是什么以及紅黑樹的結構特點，接下來在試著實現紅黑樹的結構以及實現紅黑樹插入新節點、進行節點查詢的功能，相信通過本篇的學習能讓你了解紅黑樹，一起加油把！！！

1. 紅黑樹的概念

在此紅黑樹是基于二叉搜索樹進行改進的，因此紅黑樹的中序遍歷也是有序的。

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

1.1 紅黑樹的規則

只有同時滿足以下的幾點要求時才是在紅黑樹：
1. 每個結點不是紅色就是黑色
2. 根結點是黑色的
3. 如果?個結點是紅色的，則它的兩個孩?結點必須是黑色的，也就是說任意?條路徑不會有連續的紅色結點。
4. 對于任意?個結點，從該結點到其所有NULL結點的簡單路徑上，均包含相同數量的黑色結點

以上的要求看起來是規律的，但是其實這幾點規則之間是相互協調的，接下來我們就通過幾個示例來看看這些規則是怎么使得紅黑樹當中的最長路徑的長度不大于其他路徑的兩倍的。?

來看以下的示例：

以上圖示的二叉樹當中，根節點為黑，并且不存在連續的紅節點，那么接下來就是要知道二叉樹當中每個路徑上黑節點的個數；在此之前需要我們先找出以上的二叉樹有幾條路徑，可能你會簡單的認為以上不就是有4條路徑嗎？如下所示

但是其實以上求路徑個數的方式是錯誤的，在此要一條路徑的需要到空節點為止，因此以上的正確的路徑應如下所示：


?

此時就可以看出以上的二叉樹有9條路徑，并且每條的路徑上黑色節點的個數都是2兩個，這也是滿足紅黑樹的要求的。

以上的二叉樹當中滿足了以上所示的紅黑樹的1、2、4點規則，但是對應規則3以上的所示的二叉樹的葉子節點為紅時不就不滿足規則了嗎？

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

那么在滿足紅黑樹的規則下，就可以使得沒有?條路徑會比其他路徑長出2倍，因而是接近平衡的。

以上所示的紅黑樹當中最長路徑為3，最短的為2，這時二叉搜索樹就是接近平衡的

以下的二叉搜索樹也是滿足以上的紅黑樹規則，也是紅黑樹

?這是就可以看出紅黑樹當中其實是完全沒有紅色節點的，這是也是滿足紅黑樹的規則的

1.2 紅黑樹如何保持接近平衡?

在此我們就要思考在紅黑樹是如何確保基本平衡的，也就是在紅黑樹當中是如何確保最長的路徑不超過最短路徑的兩倍的？

? 由規則4可知，從根到NULL結點的每條路徑都有相同數量的黑色結點，所以極端場景下，最短路徑就就是全是??結點的路徑，假設最短路徑長度為bh(black height)。
? 由規則2和規則3可知，任意?條路徑不會有連續的紅色結點，所以極端場景下，最長的路徑就是一黑一紅間隔組成，那么最長路徑的長度為2*bh。
? 綜合紅黑樹的4點規則而言，理論上的全?最短路徑和一黑一紅的最長路徑并不是在每棵紅?樹都存在的。假設任意?條從根到NULL結點路徑的?度為x，那么bh <= h <= 2*bh。

1.3 紅黑樹的效率?

以上我們了解了紅黑樹的概率，以及要使得二叉搜索樹為紅黑樹要滿足什么樣的要求，那么接下來就來分析在紅黑樹當中進行查找的效率。

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

?

在此紅黑樹其實相比之前學習的AVL樹控制平衡的方式不用，AVL樹是通過子樹的控制高度差進行整體的平衡控制，而紅黑樹是通過4條規則的顏色約束間接的實現近似平衡，他們效率都是同?檔次，但是相對而言，插?相同數量的結點，紅黑樹的旋轉次數是更少的，因為他對平衡的控制沒那么嚴格。在大量節點時AVL樹的高度相比紅黑樹會低一些。

2. 紅黑樹實現

以上我們了解了紅黑樹的結構特點之后接下來就來實現紅黑樹的代碼

在此創建兩個文件BRTRee.h和test.cpp，在BRTRee.h內實現紅黑樹的結構以及各種的功能，在test.cpp內對實現的紅黑樹進行測試，看是否滿足我們的要求

2.1 紅黑樹節點實現

在實現紅黑樹的結構之前我們先要實現紅黑樹節點的結構體，在此創建一個名為colour的枚舉來表示節點的顏色，創建一個名為RBTree的struct結構體來表示紅黑樹的節點，實現代碼如下所示：

enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _val;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;RBTreeNode(const pair<K, V>& val):_val(val), _left(nullptr), _right(nullptr), _parent(nullptr){}};

2.2 紅黑樹結構實現?

在實現了紅黑樹節點的結構之后，接下來我們抽獎一個名為RBTree的類，在該類內實現紅黑樹的結構以及各種功能，接下來就先實現結構，實現的代碼如下所示：

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public://各種功能……private:Node* root = nullptr;};

以上我們時使用類模板的方式來創建對應的二叉樹，這樣就可以使得創建的二叉樹內節點的數據的類型是任意的，不過要存儲在紅黑樹內的數據類型是需要能進行大小的比較，如果默認不支持也是需要我們自己實現的。

2.3 紅黑樹插入實現

以上實現了紅黑樹的大體結構之后接下來就來實現紅黑樹當中的插入功能，接下來在實現插入的代碼之前先來分析在紅黑樹當中插入新的節點會有幾種情況。

在插入新的節點之后，新形成的也是要滿足紅黑樹的4條規則的。

1.在空樹當中插入節點，那么新增的節點需要是黑色節點。

在非空的樹當中插入新的節點，此時我們就要思考應將新的節點的顏色置為黑的還是紅色？

如果我們插入的節點是紅色的那么就只需要在其父節點為紅色是進行調整，但是如果插入的節點為黑色的，這就會使得新產生的路徑內的黑色節點數比其他的路徑要多一個，這時要進行調整是很困難的，因此插入的節點應該初始化為紅節點

2.在非空樹當中插入新的節點，將該節點初始化為紅

在非空樹內插入新節點之后接下來就要看其父節點是否為紅，是的話此時的樹就違背了紅黑樹的規則3，就需要進行調整。調整直到沒有應該紅色節點的父節點為紅為止。如果一開始插入的節點的發節點就為黑；那么插入完就可以停止操作

以下就是實現的不包含調整調整代碼的插入代碼：

bool Insert(const pair <K, V> kv)
{//當插入節點時的樹為空時就將新插入的節點置為樹的根節點，且顏色變為黑if (root == nullptr){root = new Node(kv);root->_col = BLACK;return true;}//尋找合適的插入位置Node* cur = root;Node* Parent = nullptr;while (cur){if (cur->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//創建新節點cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;//進行調整使得樹滿足紅黑樹的規則……//無論以上是否進行調整都將根結點的顏色置為黑root->_col = BLACK;return true;}


?

接下來就來講解插入的節點的父節點為紅時進行調整的3種情況

注：接下來的講解當中假設我們把新增結點標識為c (cur)，c的父親標識為p(parent)，p的父親標識為g(grandfather)，p的兄弟標識為u（uncle）。

1.情況1：只需變色

當插入的節點的為父親節點為紅時，而且父親的父親的另一個節點也是紅的，也就是c節點的叔叔節點u也為紅時。因為在插入新的節點c之前當前的樹一定是滿足紅黑樹的規則的，那么此時p節點的父親節點f一定是為黑，也就是c節點的祖父節點一定為黑。

?

例如以下示例：


新插入的節點為x，此時c、p、u的節點顏色情況就滿足以上描述的形式。那么要讓該節點變回滿足紅黑樹的規則，就只需要將p、u變黑；g變紅即可。這時調整完之后就可以使得樹當中每條路徑內的黑色節點的個數都相同。

以下是只進行變色情況的抽象表達，d/e/f代表每條路徑擁有hb個黑色結點的子樹，a/b代表每條路徑擁有hb-1個黑色結點的根為紅的子樹，hb>=0。和之前學習AVL樹一樣接下來來通過看看幾種只進行變色的情況。

那么接下來就開看看 hb==0 、hb==1、hb==2的情況?，其中當hb等于2時，這?組合情況上百億種，這些樣例是幫助我們理解，不論情況多少種，多么復雜，處理方式?樣的，變?再繼續往上處理即可，所以我們只需要看抽象圖即可。

通過以上的示例就可以看出在處理只需要變色的情況時，新出現的紅色節點可能是新插入的也可能是下部分的節點調整上來的，此時只需要一直進行調整直到對應的p為黑時就停止?

實現的代碼如下所示：

以下以p節點分別為g節點的左節點和右節點的兩種情況分別進行分析
?

bool Insert(const pair <K, V> kv)
{//當插入節點時的樹為空時就將新插入的節點置為樹的根節點，且顏色變為黑if (root == nullptr){root = new Node(kv);root->_col = BLACK;return true;}//尋找合適的插入位置Node* cur = root;Node* Parent = nullptr;while (cur){if (cur->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//創建新節點cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父節點為祖父節點的左節點時//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//其他情況……}//父節點為祖父節點的右節點時//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//其他情況……}}//無論以上是否進行調整都將根結點的顏色置為黑root->_col = BLACK;return true;}

2.情況2：單旋+變色

以上情況1當中是叔叔存在且為紅的情況，那么如果叔叔不存在或者是不為紅又要怎么進行調整呢？

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

在此p是必須變為黑的，但是由于u為黑或者不存在，那么這就使得將p變為黑時p節點所在的路徑的黑色節點的個數就與其他的路徑不相同，那么這時就需要進行旋轉來解決問題。

在此也是以p節點分別為g節點的左節點和右節點的兩種情況分別進行分析

     gp    u
c

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

     gu    pc

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

3.情況3：雙旋+變色
?

以上我們分析了單旋的情，那么接下來就來分析雙旋的情況，當插入c之后紅黑樹的子樹結構如下所示時只使用單旋是無法實現調整之后的樹滿足紅黑樹的規則的，在此接下來要使用到雙旋才能調整至滿足要求。

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


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

     gp    uc

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

?

     gu    pc

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

2.4 插入完整代碼

以上我們就進行插入節點的三種情況的分析，那么接下來就將以上的插入代碼補充完整

bool Insert(const pair <K, V> kv)
{//當插入節點時的樹為空時就將新插入的節點置為樹的根節點，且顏色變為黑if (root == nullptr){root = new Node(kv);root->_col = BLACK;return true;}//尋找合適的插入位置Node* cur = root;Node* Parent = nullptr;while (cur){if (cur->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//創建新節點cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父節點為祖父節點的左節點時//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者為黑else{//當c為p的左節點時//    g//  p  u//cif (Parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//當c為p的右節點時//     g//   p   u//    celse{RotateL(Parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}//父節點為祖父節點的右節點時//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者為黑else{//當c為p的右節點時//    g//  u   p//       cif (Parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//當c為p的左節點時//    g//  u   p//     celse{RotateR(Parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}//無論以上是否進行調整都將根結點的顏色置為黑root->_col = BLACK;return true;}void RotateR(Node* Parent)
{Node* subL = Parent->_left;Node* subLR = subL->_right;if (subLR != nullptr){subLR->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_left = subLR;Parent->_parent = subL;subL->_right = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subL;}else{tmpNode->_right = subL;}subL->_parent = tmpNode;}else{root = subL;subL->_parent = nullptr;}}void RotateL(Node* Parent)
{Node* subR = Parent->_right;Node* subRL = subR->_left;if (subRL != nullptr){subRL->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_right = subRL;Parent->_parent = subR;subR->_left = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subR;}else{tmpNode->_right = subR;}subR->_parent = tmpNode;}else{root = subR;subR->_parent = nullptr;}}

2.4 紅黑樹查找

在此紅黑樹的查找實現和之前實現的二叉搜索樹和AVL樹類似，對你來說實現查找的代碼肯定是 so easy 的，在此就不再進行講解，直接奉上代碼：

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

2.5?紅黑樹刪除

在此紅黑樹的刪除較為復雜且不是很重要，在此就不進行講解。

?

2.6?紅黑樹驗證

以上我們實現了紅黑樹的插入以及查找，那么接下來就來實現驗證的代碼

首先來分析驗證的代碼該如何實現：
這力獲取最長路徑和最短路徑，檢查最長路徑不超過最短路徑的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->_val.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);
}

測試用例：

void TestAVLTree1()
{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.IsBalanceTree() << endl;cout<<t.IsBalance();
}

運行以上代碼輸出如下所示：
?

這時只能是說明對以上示例的測試用例進行插入是沒問題的，要更嚴謹的驗證就需要有更多的測試用例，這時使用以上的代碼進行驗證?，并且測試進行插入的效率以及查找效率

void TestAVLTree2()
{const int N = 1000000;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();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalance() << endl;cout << "Insert:" << end2 - begin2 << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.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 << "Find:" << end1 - begin1 << endl;
}

將vs的調整為release模式之后，通過輸出的結果就可以看出我們實現的紅黑樹的插入代碼是沒問題的，并且實現的紅黑樹的插入效率以及查找效率都是很高的，效率基本和AVL樹不差上下。?

2.7 完整代碼

RBTree.c

#pragma once
#include<iostream>using namespace std;enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _val;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;RBTreeNode(const pair<K, V>& val):_val(val), _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* cur = root;Node* Parent = nullptr;while (cur){if (cur->_val.first < kv.first){Parent = cur;cur = cur->_right;}else if (cur->_val.first > kv.first){Parent = cur;cur = cur->_left;}else{return false;}}//創建新節點cur = new Node(kv);if (Parent->_val.first < kv.first){Parent->_right = cur;}else{Parent->_left = cur;}cur->_parent = Parent;cur->_col = RED;while (Parent && Parent->_col == RED){Node* grandfather = Parent->_parent;//父節點為祖父節點的左節點時//    g//  p  u//cif (grandfather->_left == Parent){Node* uncle = grandfather->_right;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者為黑else{//當c為p的左節點時//    g//  p  u//cif (Parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//當c為p的右節點時//     g//   p   u//    celse{RotateL(Parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}//父節點為祖父節點的右節點時//    g//  u   p//       celse{Node* uncle = grandfather->_left;//叔叔存在且為紅if (uncle && uncle->_col == RED){Parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;Parent = cur->_parent;}//叔叔不存在或者為黑else{//當c為p的右節點時//    g//  u   p//       cif (Parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;Parent->_col = BLACK;}//當c為p的左節點時//    g//  u   p//     celse{RotateR(Parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}//無論以上是否進行調整都將根結點的顏色置為黑root->_col = BLACK;return true;}Node* Find(const K& val){if (root == nullptr){return nullptr;}Node* cur = root;while (cur){if (cur->_val.first < val){cur = cur->_left;}else if (cur->_val.first > val){cur = cur->_right;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(root);cout << endl;}int  Height(){return _Height(root);}int Size(){return _Size(root);}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->_val.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);}private:Node* root = nullptr;void RotateR(Node* Parent){Node* subL = Parent->_left;Node* subLR = subL->_right;if (subLR != nullptr){subLR->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_left = subLR;Parent->_parent = subL;subL->_right = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subL;}else{tmpNode->_right = subL;}subL->_parent = tmpNode;}else{root = subL;subL->_parent = nullptr;}}void RotateL(Node* Parent){Node* subR = Parent->_right;Node* subRL = subR->_left;if (subRL != nullptr){subRL->_parent = Parent;}Node* tmpNode = Parent->_parent;Parent->_right = subRL;Parent->_parent = subR;subR->_left = Parent;if (tmpNode != nullptr){if (tmpNode->_left == Parent){tmpNode->_left = subR;}else{tmpNode->_right = subR;}subR->_parent = tmpNode;}else{root = subR;subR->_parent = nullptr;}}void _InOrder(Node* cur){if (cur == nullptr){return;}_InOrder(cur->_left);cout << cur->_val.first << ":"<<cur->_val.second<<endl;_InOrder(cur->_right);}int _Height(Node* cur){if (cur == nullptr){return 0;}int Left = _Height(cur->_left);int Right = _Height(cur->_right);return Left > Right ? Left + 1 : Right + 1;}int _Size(Node* cur){if (cur == nullptr){return 0;}return 1 + _Size(cur->_left) + _Size(cur->_right);}};

test.cpp

#include<iostream>
#include<vector>
#include"BRTree.h"using namespace std;void TestAVLTree1()
{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.IsBalanceTree() << endl;cout<<t.IsBalance();
}void TestAVLTree2()
{const int N = 1000000;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();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalance() << endl;cout << "Insert:" << end2 - begin2 << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.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 << "Find:" << end1 - begin1 << endl;
}int main()
{//TestAVLTree1();TestAVLTree2();return 0;
}

以上就是本篇的全部內容了，在實現了紅黑樹之后接下來我們就可以基于紅黑樹來自己實現封裝set和map，未完待續……

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/73335.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/73335.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/73335.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【第23節】windows網絡編程模型(WSAEventSelect模型)

【第23節】windows網絡編程模型(WSAEventSelect模型)

目錄 引言 一、WSAEventSelect模型概述 二、 WSAEventSelect模型的實現流程 2.1 創建一個事件對象&#xff0c;注冊網絡事件 2.2 等待網絡事件發生 2.3 獲取網絡事件 2.4 手動設置信號量和釋放資源 三、 WSAEventSelect模型偽代碼示例 四、完整實踐示例代碼 引言 在網…
閱讀更多...
概率預測之NGBoost（Natural Gradient Boosting）回歸和分位數（Quantile Regression）回歸

概率預測之NGBoost（Natural Gradient Boosting）回歸和分位數（Quantile Regression）回歸

概率預測之NGBoost（Natural Gradient Boosting）回歸和線性分位數回歸 NGBoostNGBoost超參數解釋NGBoost.fitscore(X, Y)staged_predict(X)feature_importances_pred_dist 方法來獲取概率分布對象分位數回歸（Quantile Regression）smf.quantreg 對多變量數據進行分位數回歸分…
閱讀更多...
手撕算法——鏈表

手撕算法——鏈表

算法基礎——鏈表-CSDN博客 一、排隊順序 題?來源&#xff1a;洛? 題?鏈接&#xff1a;B3630 排隊順序 - 洛谷 難度系數&#xff1a;★ 1. 題目描述 2. 算法原理 本題相當于告訴了我們每?個點的后繼&#xff0c;使?靜態鏈表的存儲?式能夠很好的還原這個隊列。 數組中 [1,…
閱讀更多...
RAG優化：python從零實現[吃一塹長一智]循環反饋Feedback

RAG優化：python從零實現[吃一塹長一智]循環反饋Feedback

本文將介紹一種有反饋循環機制的RAG系統，讓當AI學會"吃一塹長一智"，給傳統RAG裝了個"后悔"系統，讓AI能記住哪些回答被用戶點贊/拍磚，從此告別金魚記憶： 每次回答都像在玩roguelike：失敗結局會強化下次冒險悄悄把優質問答變成新知識卡牌，實現"以…
閱讀更多...
kotlin init執行順序

kotlin init執行順序

一 代碼 kotlin: package test.fclass Test1 { }class TestInit(s: String, i: Int) {var name: String? nullvar age 0private var a :Int 1init {this.name sthis.age iprintln("init代碼塊: $name, $age")}}轉成java // Test1.java package test.f;import…
閱讀更多...
使用cursor開發java案例——springboot整合elasticsearch

使用cursor開發java案例——springboot整合elasticsearch

安裝elasticsearch 打開cursor&#xff0c;輸入如下提示詞 使用springboot整合elasticsearch。其中elasticsearch服務器ip&#xff1a;192.168.236.134 管理員用戶名elastic 管理員密碼 PdQy_xfR2yLhpok*MK_ 監聽端口9200點Accept all 使用idea打開生成的項目 &#xff0…
閱讀更多...
Java Collection API增強功能系列之一 Arrays.asList()

Java Collection API增強功能系列之一 Arrays.asList()

在Java編程中&#xff0c;Arrays.asList() 是一個高頻使用卻又容易引發陷阱的工具方法。它能夠快速將數組轉換為列表&#xff0c;但其特殊行為常常讓開發者踩坑。本文將深入剖析該方法的本質特性&#xff0c;并揭示其使用時的注意事項。一、方法定義與基礎用法 1. 方法簽名 p…
閱讀更多...
vue3 項目的最新eslint9 + prettier 配置

vue3 項目的最新eslint9 + prettier 配置

注意&#xff1a;eslint目前升級到9版本了 在 ESLint v9 中&#xff0c;配置文件已經從 .eslintrc 遷移到了 eslint.config.js 配置的方式和之前的方式不太一樣了&#xff01;&#xff01;&#xff01;&#xff01; 詳見自己的語雀文檔&#xff1a;5、新版eslint9prettier 配…
閱讀更多...
基于FPGA的16QAM+幀同步系統verilog開發,包含testbench,高斯信道,誤碼統計,可設置SNR

基于FPGA的16QAM+幀同步系統verilog開發,包含testbench,高斯信道,誤碼統計,可設置SNR

目錄 1.算法仿真效果 2.算法涉及理論知識概要 2.1 16QAM調制解調原理 2.2 幀同步 3.Verilog核心程序 4.完整算法代碼文件獲得 1.算法仿真效果 vivado2019.2仿真結果如下&#xff08;完整代碼運行后無水印&#xff09;&#xff1a; 設置SNR12db 將FPGA數據導入到MATLAB顯…
閱讀更多...
[學成在線]06-視頻分片上傳

[學成在線]06-視頻分片上傳

上傳視頻 需求分析 教學機構人員進入媒資管理列表查詢自己上傳的媒資文件。 點擊“媒資管理” 進入媒資管理列表頁面查詢本機構上傳的媒資文件。 教育機構用戶在"媒資管理"頁面中點擊 "上傳視頻" 按鈕。 點擊“上傳視頻”打開上傳頁面 選擇要上傳的文件…
閱讀更多...
Maven安裝與環境配置

Maven安裝與環境配置

首先我們先介紹一些關于Maven的知識&#xff0c;如果著急直接看下面的安裝教程。 目錄 Maven介紹 Maven模型 Maven倉庫 Maven安裝 下載 安裝步驟 Maven介紹 Apache Maven是一個項目管理和構建工具&#xff0c;它基于項目對象模型(Project Object Model , 簡稱: POM)的概念…
閱讀更多...
【新能源汽車溫度采集與控制系統設計深度解析】

【新能源汽車溫度采集與控制系統設計深度解析】

面向汽車行業研發與測試測量設備從業者的技術指南 一、硬件架構設計 新能源汽車的溫度采集與控制系統是保障電池、電機、電控等核心部件安全運行的核心技術之一。其硬件架構需兼顧高精度、抗干擾、可靠性與集成化&#xff0c;以下從信號調理電路、ADC模塊、隔離設計三個維度展…
閱讀更多...
AI Tokenization

AI Tokenization

AI Tokenization 人工智能分詞初步了解 類似現在這個&#xff0c;一格子 一格子&#xff0c;拼接出來的&#xff0c;一行或者一句&#xff0c;像不像&#xff0c;我們人類思考的時候組裝出來的話&#xff0c;并用嘴說出來了呢。
閱讀更多...
React(四）setState原理-性能優化-ref

React(四）setState原理-性能優化-ref

setState詳解 實現原理 開發中我們并不能直接修改State來重新渲染界面&#xff1a; 因為修改State之后&#xff0c;希望React根據最新的State來重新渲染界面&#xff0c;但這種方式的修改React并不知道數據發生了變化&#xff1b; React并沒有類似于Vue2中的Object.defineP…
閱讀更多...
SSH密鑰認證 + 文件系統權限控制 + Git倉庫配置+封存與解封GIT倉庫

SSH密鑰認證 + 文件系統權限控制 + Git倉庫配置+封存與解封GIT倉庫

在本地服務器上實現多個用戶僅通過git push操作修改倉庫、禁止其他改寫方式的需求&#xff0c;可以通過以下步驟實現&#xff1a; 方法概述 通過SSH密鑰認證 文件系統權限控制 Git倉庫配置&#xff0c;確保用戶僅能通過git push命令提交修改&#xff0c;而無法通過直接操作服…
閱讀更多...
全文通讀：126頁華為IPD集成產品開發與DFX實戰【文末附可編輯PPT下載鏈接】

全文通讀：126頁華為IPD集成產品開發與DFX實戰【文末附可編輯PPT下載鏈接】

綁定資料內容： 12023華為流程體系及落地實施【108頁 PPT】.pptx22024版基于華為IPD與質量管理體系融合的研發質量管理【63頁】.pptx
閱讀更多...
//TODO 動態代理的本質?

//TODO 動態代理的本質?

待解決 //TODO 面試題 為啥mybatis的mapper只有接口沒有實現類&#xff0c;但它卻能工作&#xff1f;?(ai參考,待深究源碼) 1. 動態代理生成代理對象 MyBatis 使用 JDK 動態代理 為每個 Mapper 接口生成代理對象&#xff1a; ? 核心類&#xff1a;MapperProxy&#xff08;…
閱讀更多...
C++11中智能指針的使用(shared_ptr、unique_ptr、weak_ptr)

C++11中智能指針的使用(shared_ptr、unique_ptr、weak_ptr)

C11中智能指針的使用(shared_ptr、unique_ptr、weak_ptr) 一、shared_ptr原理 shared_ptr 是另一種智能指針&#xff0c;用于實現多個 shared_ptr 實例共享同一個對象的所有權。它通過內部的控制塊&#xff08;通常是一個包含計數器和指向對象的指針的結構&#xff09;來管理…
閱讀更多...
2024年認證杯SPSSPRO杯數學建模B題(第二階段)神經外科手術的定位與導航全過程文檔及程序

2024年認證杯SPSSPRO杯數學建模B題(第二階段)神經外科手術的定位與導航全過程文檔及程序

2024年認證杯SPSSPRO杯數學建模 B題 神經外科手術的定位與導航 原題再現&#xff1a; 人的大腦結構非常復雜&#xff0c;內部交織密布著神經和血管&#xff0c;所以在大腦內做手術具有非常高的精細和復雜程度。例如神經外科的腫瘤切除手術或血腫清除手術&#xff0c;通常需要…
閱讀更多...
嘗試在軟考62天前開始成為軟件設計師-信息系統安全

嘗試在軟考62天前開始成為軟件設計師-信息系統安全

安全屬性 保密性:最小授權原則(能干活的最小權限)、防暴露(隱藏)、信息加密、物理保密完整性(防篡改):安全協議、校驗碼、密碼校驗、數字簽名、公證 可用性:綜合保障( IP過濾、業務流控制、路由選擇控制、審計跟蹤)不可抵賴性:數字簽名 對稱加密 DES :替換移位 3重DESAESR…
閱讀更多...
最新文章

Copyright @ 2022~2023