目錄

00.引入

01.紅黑樹的性質(zhì)

02.紅黑樹的定義

03.紅黑樹的插入

1.按照二叉搜索樹的規(guī)則插入新節(jié)點

2.檢測新節(jié)點插入后，是否滿足紅黑樹的性質(zhì)

1.uncle節(jié)點存在且為紅色

2.uncle節(jié)點不存在

3.uncle節(jié)點存在且為黑色

?04.驗證紅黑樹

---

00.引入

和AVL樹一樣，紅黑樹也是一種自平衡的二叉搜索樹。AVL樹通過平衡因子調(diào)整子樹的高度，確保樹的高度差在 -1 到 1 之間。而紅黑樹通過在每個節(jié)點上增加一個存儲位表示節(jié)點的顏色，可以是RED或BLACK。通過對任何一條從根到葉子的路徑上各個節(jié)點著色方式的限制，紅黑樹確保沒有任何一條路徑會是其他路徑的兩倍以上長，因而接近平衡。

01.紅黑樹的性質(zhì)

紅黑樹具有以下幾種性質(zhì)，這些性質(zhì)確保了樹的平衡性和高效性：

1.節(jié)點顏色：每個節(jié)點要么是紅色，要么是黑色。

2.根節(jié)點顏色：根節(jié)點始終是黑色。

3.紅色節(jié)點限制：沒有兩個紅色節(jié)點可以相連。

4.黑色節(jié)點數(shù)量：從任何節(jié)點到其每個葉子節(jié)點的所以路徑包含相同數(shù)量的黑色節(jié)點。

5.葉子節(jié)點：所有的葉子節(jié)點（此處都表示為NULL節(jié)點）都是黑色。

其實還有一條潛規(guī)則：每一個新插入的節(jié)點初始都為紅色。

為什么以上性質(zhì)就可以保證最長路徑的節(jié)點個數(shù)不會超過最短路徑節(jié)點個數(shù)的兩倍？

通過性質(zhì)1/2/5可知，在判斷性質(zhì)4時（計算路徑上黑色節(jié)點的數(shù)量），不需要考慮頭節(jié)點以及葉子節(jié)點，只需要考慮中間節(jié)點即可，再根據(jù)性質(zhì)3，可以列舉以下幾種情況：

1.中間沒有黑色節(jié)點：

路徑： 黑->黑，黑->紅->黑。

2.中間只有1個黑色節(jié)點：

路徑：?黑->黑->黑，黑->紅->黑->黑，黑->黑->紅->黑，黑->紅->黑->紅->黑

3.中間有2個黑色節(jié)點：

路徑：?黑->黑->黑->黑，黑->紅->黑->黑->黑，黑->黑->紅->黑->黑，黑->黑->黑->紅->黑

? ? ? ? ? ? 。。。黑->紅->黑->紅->黑->紅->黑

可以看出，最短路徑就是全黑的；最長路徑是黑、紅相間的。因而我們可以找到規(guī)律：

假設中間有n個黑色節(jié)點：

最短路徑：n+2（中間節(jié)點加上首尾）

最長路徑：n+(n+1)+2=2n+3（中間有n個黑色節(jié)點最多可以有n+1個紅色節(jié)點）

所以最長路徑（2n+3）永遠比最短路徑的2倍（2n+4）小1。

02.紅黑樹的定義

紅黑樹的底層結(jié)構(gòu)在代碼實現(xiàn)中使用節(jié)點結(jié)構(gòu)體和數(shù)來表示。節(jié)點結(jié)構(gòu)體?保存每個節(jié)點的數(shù)據(jù)、指向左右子節(jié)點、父節(jié)點的指針、以及平衡因子；樹類管理插入、刪除等操作。

// 節(jié)點的顏色
enum Color { RED, BLACK };// 紅黑樹節(jié)點的定義
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data = T(), Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<T>* _pLeft; // 節(jié)點的左孩子RBTreeNode<T>* _pRight; // 節(jié)點的右孩子RBTreeNode<T>* _pParent; // 節(jié)點的雙親T _data; // 節(jié)點的值域Color _color; // 節(jié)點的顏色
};

在節(jié)點的定義中，我們將節(jié)點默認顏色給成紅色，這是因為如果定義成黑色的話，根據(jù)性質(zhì)4，每一次插入節(jié)點都需要重新調(diào)整樹，而定義成紅色，就只需要在父節(jié)點也為紅色時進行調(diào)整，一定程度上保證了插入的效率。

03.紅黑樹的插入

紅黑樹是在二叉搜索樹的基礎上加上平衡限制條件的，因此紅黑樹的插入可以分為兩步：

1.按照二叉搜索樹的規(guī)則插入新節(jié)點

	// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false// 注意：為了簡單起見，本次實現(xiàn)紅黑樹不存儲重復性元素bool Insert(const T& data){if (!_pRoot) // 根節(jié)點為空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 設置根節(jié)點為黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重復，不進行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父節(jié)點的子節(jié)點指針if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;return true;}

二叉搜索樹的插入過程不在贅述，詳細可跳轉(zhuǎn)這篇博客【C++】二叉搜索樹。

2.檢測新節(jié)點插入后，是否滿足紅黑樹的性質(zhì)

因為新插入節(jié)點默認為紅色，因此如果雙親節(jié)點是黑色，則滿足性質(zhì)，不需要調(diào)整；如果雙親節(jié)點為紅色，違反了性質(zhì)3，需要進行調(diào)整，調(diào)整過程需要進行分類討論：

第一種情況：

我們調(diào)整紅黑樹的底層邏輯是通過改變某些節(jié)點的顏色，使整棵樹符合性質(zhì)，看下面這棵樹：

cur表示新插入節(jié)點，parent為父節(jié)點，grandpa為父節(jié)點的父節(jié)點，uncle為grandpa的另一個節(jié)點

（下面用c，p，g，u分別表示cur，parent，grandpa，uncle）

此時c和p是連續(xù)的紅色節(jié)點。破壞了性質(zhì)3，那么我直接把p的顏色改成黑色，性質(zhì)3被修復，但同時又破壞了性質(zhì)4，于是我把u的顏色也改成黑色，這樣以g為根節(jié)點的這棵樹確實被修復了。

但要注意，如果g不是根節(jié)點呢

此時性質(zhì)4還是被破壞了，為此，把g的顏色改成紅色

這樣就完成了修復。但如果是下面這種情況呢

g的雙親也為紅色，此時需要繼續(xù)向上調(diào)整。。

所以我們得到了第一種情況：

1.uncle節(jié)點存在且為紅色

a.祖父節(jié)點為根 或 祖父的雙親為黑色

只需要修改u和p的顏色即可

b.祖父節(jié)點不為根 且 祖父的雙親為紅色

此時需要進一步向上調(diào)整

將cur的位置換到grandpa，p、u、g一并轉(zhuǎn)換，此時u一定存在，如果u不存在，則違反了性質(zhì)4

第二種情況：

2.uncle節(jié)點不存在

1.單旋的情況

學習過AVL樹可以知道，對于這樣的一棵樹我們需要通過旋轉(zhuǎn)的方法調(diào)整高度，關(guān)于旋轉(zhuǎn)的原理，可以調(diào)整這篇博客【C++】AVL樹

旋轉(zhuǎn)完成之后，我們需要調(diào)整顏色，此時p成為了這棵樹的根節(jié)點，為了滿足條件4，我們把p顏色改成黑，g顏色改成紅：

這是左單旋的情況，右單旋同理

2.雙旋的情況

雙旋分為 右左 與 左右 兩種情況，右左即p是g的右孩子，c是p的左孩子。右左情況下我們需要對p進行右單旋，在對g進行左單旋，最后調(diào)整c和g的顏色，過程如下：

左右的情況同理

3.uncle節(jié)點存在且為黑色

a.單旋的情況

此時cur一定不是新插入節(jié)點，這種情況就是1.b向上調(diào)整的后續(xù)了，此時依舊要用到旋轉(zhuǎn)操作，和情況2同理：

b.雙旋的情況

由此看來，情況2和情況3其實可以合并。

下面給出插入以及旋轉(zhuǎn)的完整代碼：

template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree(){_pRoot = nullptr;}// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false// 注意：為了簡單起見，本次實現(xiàn)紅黑樹不存儲重復性元素bool Insert(const T& data){if (!_pRoot) // 根節(jié)點為空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 設置根節(jié)點為黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重復，不進行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父節(jié)點的子節(jié)點指針if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;while (pParent && pParent->_color == RED){Node* pGrandpa = pParent->_pParent;if (!pGrandpa)pParent->_color = BLACK;else {if (pParent == pGrandpa->_pRight) {Node* pUncle = pGrandpa->_pLeft;// uncle存在且為紅if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 繼續(xù)向上調(diào)整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle為黑else{// 右右的情況if (pCur == pParent->_pRight){RotateL(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 右左的情況else{RotateR(pParent);RotateL(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}else // pParent = pGrandpa->_pLeft{Node* pUncle = pGrandpa->_pRight;// uncle存在且為紅if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 繼續(xù)向上調(diào)整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle為黑else{// 左左的情況if (pCur == pParent->_pLeft){RotateR(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 左右的情況else{RotateL(pParent);RotateR(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}}}_pRoot->_color = BLACK;return true;}private:// 左單旋void RotateL(Node* pParent){Node* pCur = pParent->_pRight;pParent->_pRight = pCur->_pLeft; // cur的左孩子作為parent的右孩子if (pCur->_pLeft)pCur->_pLeft->_pParent = pParent;if (pParent->_pParent) // parent不是根節(jié)點{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根節(jié)點{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pLeft = pParent;}// 右單旋void RotateR(Node* pParent){Node* pCur = pParent->_pLeft;pParent->_pLeft = pCur->_pRight; // cur的右孩子作為parent的左孩子if (pCur->_pRight)pCur->_pRight->_pParent = pParent;if (pParent->_pParent) // parent不是根節(jié)點{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根節(jié)點{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pRight = pParent;}private:Node* _pRoot;
};

?04.驗證紅黑樹

檢驗上述代碼，就得從紅黑樹的5條性質(zhì)入手，性質(zhì)1、5不需要驗證，性質(zhì)2也很容易驗證，實際上我們主要驗證的是性質(zhì)3（沒有連續(xù)的紅色節(jié)點）以及性質(zhì)4（每條路徑上黑色節(jié)點數(shù)量一致）

對于性質(zhì)4，我們可以先記錄某一條路徑（這里選取最左葉節(jié)點這條路徑）的黑色節(jié)點數(shù)量，再遍歷每一條路徑，只要有一條路徑上的黑色節(jié)點數(shù)量與前者不一樣，就返回false，這里選擇用遞歸的方式遍歷紅黑樹。

對于性質(zhì)3，我們需要再遍歷的過程中，碰到紅色節(jié)點，就驗證一下雙親的顏色，如果也為紅，則違反性質(zhì)，返回false

完整代碼如下：

	// 檢測紅黑樹是否為有效的紅黑樹，注意：其內(nèi)部主要依靠_IsValidRBTRee函數(shù)檢測bool IsValidRBTRee(){if (!_pRoot)return true;if (RED == _pRoot->_color)return false;Node* pCur = _pRoot;size_t blackcount = 0;while (pCur){if (BLACK == pCur->_color)++blackcount;pCur = pCur->_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到達葉子節(jié)點，檢查黑色節(jié)點數(shù)量return pathBlack == blackCount;}// 檢查當前節(jié)點的顏色if (pRoot->_color == RED) {// 如果是紅色，檢查父節(jié)點是否也是紅色if (pRoot->_pParent && pRoot->_pParent->_color == RED) {return false; // 違反紅黑樹性質(zhì)}}// 更新路徑上的黑色節(jié)點數(shù)量if (pRoot->_color == BLACK) {pathBlack++;}// 遞歸檢查左子樹和右子樹return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);}

最后我們用一萬組包含10個1~100隨機數(shù)的數(shù)組驗證紅黑樹：

#include<iostream>
using namespace std;
#include"My_RBTree.h"
#include<vector>bool test1()
{srand(time(0));  // 初始化隨機種子// 生成10000組隨機向量for (int i = 0; i < 10000; ++i) {RBTree<int> BT;vector<int> nums;// 每組隨機生成10個整數(shù)（范圍為 1 到 100）for (int j = 0; j < 10; ++j) {nums.push_back(rand() % 100 + 1);}// 將每個整數(shù)插入 B 樹中for (const int& num : nums) {BT.Insert(num);}// 檢查 B 樹if (!BT.IsValidRBTRee()) {cout << "樹不平衡，測試失敗！\n";for (auto it : nums){cout << it << ", ";}cout << endl;return 1;}}cout << "所有10000組隨機樹均平衡，測試通過！\n";
}int main()
{test1();return 0;
}

運行結(jié)果：

驗證通過！

附上完整代碼：

//My_RBTree.h
#pragma once
// 節(jié)點的顏色
enum Color { RED, BLACK };// 紅黑樹節(jié)點的定義
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data = T(), Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<T>* _pLeft; // 節(jié)點的左孩子RBTreeNode<T>* _pRight; // 節(jié)點的右孩子RBTreeNode<T>* _pParent; // 節(jié)點的雙親T _data; // 節(jié)點的值域Color _color; // 節(jié)點的顏色
};template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree(){_pRoot = nullptr;}// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false// 注意：為了簡單起見，本次實現(xiàn)紅黑樹不存儲重復性元素bool Insert(const T& data){if (!_pRoot) // 根節(jié)點為空直接插入{_pRoot = new Node(data);_pRoot->_color = BLACK; // 設置根節(jié)點為黑色return true;}Node* pParent = nullptr;Node* pCur = _pRoot;while (pCur){pParent = pCur;if (data == pCur->_data) // 元素重復，不進行插入return false;else if (data > pCur->_data) // 大于向右走pCur = pCur->_pRight;else // 小于向左走pCur = pCur->_pLeft;}pCur = new Node(data);// 更新父節(jié)點的子節(jié)點指針if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;pCur->_pParent = pParent;while (pParent && pParent->_color == RED){Node* pGrandpa = pParent->_pParent;if (!pGrandpa)pParent->_color = BLACK;else {if (pParent == pGrandpa->_pRight) {Node* pUncle = pGrandpa->_pLeft;// uncle存在且為紅if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 繼續(xù)向上調(diào)整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle為黑else{// 右右的情況if (pCur == pParent->_pRight){RotateL(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 右左的情況else{RotateR(pParent);RotateL(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}else // pParent = pGrandpa->_pLeft{Node* pUncle = pGrandpa->_pRight;// uncle存在且為紅if (pUncle && pUncle->_color == RED){pUncle->_color = pParent->_color = BLACK;pGrandpa->_color = RED;// 繼續(xù)向上調(diào)整pCur = pGrandpa;pParent = pCur->_pParent;}// uncle不存在或者uncle為黑else{// 左左的情況if (pCur == pParent->_pLeft){RotateR(pGrandpa);pParent->_color = BLACK;pGrandpa->_color = RED;}// 左右的情況else{RotateL(pParent);RotateR(pGrandpa);pCur->_color = BLACK;pGrandpa->_color = RED;}break;}}}}_pRoot->_color = BLACK;return true;}// 檢測紅黑樹中是否存在值為data的節(jié)點，存在返回該節(jié)點的地址，否則返回nullptrNode* Find(const T& data){Node* pCur = _pRoot;while (pCur){if (data == pCur->_data)return pCur;if (data > pCur->_data)pCur = pCur->_pRight;elsepCur = pCur->_pLeft;}return nullptr;}// 檢測紅黑樹是否為有效的紅黑樹，注意：其內(nèi)部主要依靠_IsValidRBTRee函數(shù)檢測bool IsValidRBTRee(){if (!_pRoot)return true;if (RED == _pRoot->_color)return false;Node* pCur = _pRoot;size_t blackcount = 0;while (pCur){if (BLACK == pCur->_color)++blackcount;pCur = pCur->_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到達葉子節(jié)點，檢查黑色節(jié)點數(shù)量return pathBlack == blackCount;}// 檢查當前節(jié)點的顏色if (pRoot->_color == RED) {// 如果是紅色，檢查父節(jié)點是否也是紅色if (pRoot->_pParent && pRoot->_pParent->_color == RED) {return false; // 違反紅黑樹性質(zhì)}}// 更新路徑上的黑色節(jié)點數(shù)量if (pRoot->_color == BLACK) {pathBlack++;}// 遞歸檢查左子樹和右子樹return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);}// 左單旋void RotateL(Node* pParent){Node* pCur = pParent->_pRight;pParent->_pRight = pCur->_pLeft; // cur的左孩子作為parent的右孩子if (pCur->_pLeft)pCur->_pLeft->_pParent = pParent;if (pParent->_pParent) // parent不是根節(jié)點{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根節(jié)點{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pLeft = pParent;}// 右單旋void RotateR(Node* pParent){Node* pCur = pParent->_pLeft;pParent->_pLeft = pCur->_pRight; // cur的右孩子作為parent的左孩子if (pCur->_pRight)pCur->_pRight->_pParent = pParent;if (pParent->_pParent) // parent不是根節(jié)點{pCur->_pParent = pParent->_pParent;if (pParent->_pParent->_pLeft == pParent)pParent->_pParent->_pLeft = pCur;elsepParent->_pParent->_pRight = pCur;}else // parent是根節(jié)點{_pRoot = pCur;pCur->_pParent = nullptr;}pParent->_pParent = pCur;pCur->_pRight = pParent;}private:Node* _pRoot;
};

//test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;#include"My_RBTree.h"#include<vector>bool test1(){srand(time(0));  // 初始化隨機種子// 生成10000組隨機向量for (int i = 0; i < 10000; ++i) {RBTree<int> BT;vector<int> nums;// 每組隨機生成10個整數(shù)（范圍為 1 到 100）for (int j = 0; j < 10; ++j) {nums.push_back(rand() % 100 + 1);}// 將每個整數(shù)插入 B 樹中for (const int& num : nums) {BT.Insert(num);}// 檢查 B 樹if (!BT.IsValidRBTRee()) {cout << "樹不平衡，測試失敗！\n";for (auto it : nums){cout << it << ", ";}cout << endl;return 1;}}cout << "所有10000組隨機樹均平衡，測試通過！\n";}void test2(){RBTree<int> BT1;vector<int> v1 = { 70,25,97,18,51,85 };for (auto it : v1){BT1.Insert(it);}cout << BT1.IsValidRBTRee() << endl;}int main(){test1();return 0;}

以上就是紅黑樹的詳解與模擬實現(xiàn)過程，歡迎在評論區(qū)留言，碼文不易，覺得這篇博客對你有幫助的，可以點贊收藏關(guān)注支持一波~😉