C++數據結構紅黑樹全面分析
⭐️博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
🌏概念和性質
紅黑樹的概念： 紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。它是通過控制節點顏色的方式來控制這棵樹的相對平衡，保證瞭沒有一條路徑會比其它路徑長出兩倍。
紅黑樹的性質：
- 結點是紅色或黑色。
- 根結點是黑色。
- 所有葉子都是黑色。（葉子是空結點）
- 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
- 從任一節結點到其每個葉子的所有路徑都包含相同數目的黑色結點
上面的五個性質還可以用更通俗的語言描述為三句話：
- 根節點是黑色的
- 沒有連續的紅節點
- 每條路徑的黑節點數目相同（每條路徑指的是從根節點到黑色的空節點）
思考： 為什麼紅黑樹中最長路徑的長度不會超過最短路徑節點個數的兩倍？
最長路徑： 該條路徑上節點分佈是一紅一黑
最短路徑： 該條路徑上節點分佈是全黑
假設每條路徑黑色節點數為N，則最長路徑為2N，最短路徑為N，所以這樣就推出紅黑樹中最長路徑的長度不會超過最短路徑節點個數的兩倍。
🌏紅黑樹的實現
🌲紅黑樹節點定義
這裡也是一個三叉鏈，其中每個節點包含顏色的元素在裡面：
enum Color
{
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;
Color _color;
RBTreeNode(const pair<K, V>& kv, Color color = RED)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _color(color)
{}
};
🌲紅黑樹結構定義
裡面隻包含一個根節點的成員變量，和前面兩棵樹的結構定義沒有什麼大的區別，區別在於節點的定義：
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
🌲紅黑樹的插入
🍯方法概述
第一步： 我們先按照二叉搜索樹樹插入節點的方式，插入節點
第二步： 為瞭不破壞紅黑樹的規則，我們插入節點後要對紅黑樹進行相應的調整
思考： 我們插入節點應該默認插入紅色節點好還是黑色節點好呢？ 答案是紅色節點。為什麼呢？我們要考慮哪種方式對紅黑樹的破壞性更大一點。如果是黑色，此時黑導致該條路徑比其它路徑上黑色節點數都多一個，這樣下來調整紅黑樹的步驟代價似乎會有點大；如果是紅色，不會破壞規則5，隻是破壞規則4，可能會出現連續的紅色節點，這樣我們隻需要調整該節點及其附近節點的顏色即可，代價沒有前一種方式大，所以我們選擇第二種方式。
🍯調整節點顏色
第一種情況： 如果插入節點的父親是黑色節點，那麼可以直接結束，不需要繼續調整瞭
第二種情況： 如果插入節點為的父親為紅色節點，就需要進行相應的調整 下面討論父親節點是祖父節點的左孩子的幾種情形（是右孩子的情形和這個類型，大傢可以自己推演一下，這裡我們把父親節點叫做p(parent)，祖父叫g(grandfather)，叔叔節點叫u(uncle)）：
情況1： p為紅色（g肯定是存在的且為黑），u存在且為紅
操作： 把p和u改成黑，g改成紅，如果g為根節點就把g的顏色變成黑然後結束，如果g不為根節點，且g的父親為黑色也節數，為紅色就需要迭代向上調整，判斷此時處於何種情況 具像圖：
如果g的父親為紅，就迭代向上調整：cur = grandfather,grandfather = grandfather->parent
抽象圖：抽象圖中cur可能是新插入的節點，也可能是迭代調整上來的節點，這裡g這棵子樹每條路徑黑色節點數是相同的，且調整後g這棵子樹的每條路徑黑色數相同且和之前一樣。cur是parent的左孩子和右孩子是一樣的，因為這裡都是對顏色進行控制，和方向無關。
情況2： p為紅色（g肯定是存在的且為黑），u不存在
操作： cur為parent的左孩子時，對g進行右單旋，然後將p的顏色改黑，g的顏色改紅；cur為parent的右孩子時，先對p進行左單旋，然後對g進行右單旋，然後將cur的顏色改黑，g的顏色改紅 具象圖：此時cur一定為新增節點，因為g的右子樹沒有黑節點，所以cur的下面也不可能有黑節點 cur為parent的左孩子時 一條直線，此時進行右單旋
cur為parent的左孩子時 一條折線，此時進行左右雙旋
上面的第二種情況可以先進行左單旋，然後交換cur和p，把折線變為直線，最後都執行直線的情況。
情況3： p為紅色（g肯定是存在的且為黑），u存在且為黑
操作： 如果cur為parent的左孩子，對g進行右單旋，然後將p的顏色改為黑，g的顏色改為紅；如果cur為parent的右孩子，先對p進行左單旋，對g進行右單旋，然後將cur的顏色改為黑，g的顏色改為紅
解釋： 假設此時a和b中黑色節點數為a，c的黑色節點數也一定為a，d和e的黑色節點數就是a-1，調整後cur和g的抽象圖的黑色節點都是a，整體相等。 抽象圖：此時cur一定為調整上來的節點，因為如果是新增節點的話，那麼原來g這棵子樹左右黑色節點數目不等，所以cur一定是調整上來的節點。 cur為parent的左孩子 一條直線，進行右單旋即可
cur為parent的右孩子 一條折線，此時進行左右雙旋
和情況2一樣，上面的第二種情況可以先進行左單旋，然後交換cur和p，把折線變為直線，最後都執行直線的情況。
總結： 上面就是p是g的左孩子的所有情形，為g的右孩子是與這個類似。還有註意的是根節點最後一定要改為黑色。
🍯插入代碼實現
旋轉代碼如下： 這裡就是上一篇博客的旋轉代碼，具體如下
// 左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// parent的右指向subR的左
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (ppNode == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
}
// 右單旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// parent的左指向subL的右
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (ppNode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
}
插入代碼實現如下：
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv, BLACK);// 根節點默認給黑
return make_pair(_root, true);
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (kv.first < cur->_kv.first)
cur = cur->_left;
else if (kv.first > cur->_kv.first)
cur = cur->_right;
else
return make_pair(nullptr, false);
}
// 節點默認給紅節點，帶來的影響更小
// 給黑節點的話會影響 每條路徑的黑節點相同這條規則
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 調整顏色
// 情況一：p是紅，g是黑，u存在且為紅
// 調整後的幾種情況：
// 1.如果g為根節點，把g的顏色改成黑，結束；
// 2.如果g不為根節點，
// a.g的父節點為黑，結束；
// b.g的父節點為紅，迭代向上調整,繼續判斷是哪種情況（一和三）
// cur = grandfather;
// father = cur->father;
// 這裡不管cur是在p的左邊還是右邊，都是一樣的，關心的是顏色而不是位置
// 情況二：p是紅，g是黑，u不存在/u為黑 cur p g 三個是一條直線
// 調整方法（左邊為例）：1.右單旋 2.把p改成黑，g改成紅
// a. u不存在時，cur必定是新增節點
// b. u存在時，cur必定是更新上來的節點
// 情況三：p是紅，g是黑，u不存在/u為黑 cur p g 三個是一條折線
// 調整方法（左邊為例）：1.p左單旋 2.g右單旋 3.把cur改成黑，g改成紅
// a. u不存在時，cur必定是新增節點
// b. u存在時，cur必定是更新上來的節點
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
// 左邊
if (grandfather->_left == parent)
{
// 紅黑色的條件關鍵看叔叔
Node* uncle = grandfather->_right;
// u存在且為紅
if (uncle && uncle->_color == RED)
{
// 調整 p和u改成黑，g改成紅
parent->_color = uncle->_color = BLACK;
grandfather->_color = RED;
// 迭代 向上調整
cur = grandfather;
parent = cur->_parent;
}
else// u存在為黑/u不存在
{
// 折線用一個左單旋處理 1.p左單旋 2.g右單旋 3.把cur改成黑，g改成紅 cur p g 三個是一條折線
if (cur == parent->_right)
{
RotateL(parent);
swap(parent, cur);
}
// 直線 cur p g 把p改成黑，g改成紅
// 右單旋 有可能是第三種情況
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
}
}
// uncle在左邊
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
grandfather->_color = RED;
// 迭代 向上調整
cur = grandfather;
parent = cur->_parent;
}
else
{
// 折線用一個右單旋處理 g p cur g變紅p邊黑
if (cur == parent->_left)
{
RotateR(parent);
swap(parent, cur);
}
// 直線 g p cur 把p改成黑，g改成紅
// 左單旋 有可能是第三種情況
RotateL(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
}
}
}
_root->_color = BLACK;
return Find(kv.first);
}
🌲紅黑樹的刪除
🍯方法概述
第一步： 先按照二叉搜索樹刪除節點的方式找到要刪除節點（也可能是替代節點）
第二步： 然後為瞭不破壞紅黑樹的幾條規則，要對節點的顏色進行相應地調整
🍯調整顏色
第一種情況： 刪除節點（也可能是替代節點）（之後都叫delNode），如果該節點為紅色，則直接刪除退出即可，delNode沒找到也可以直接退出
第二種情況： delNode為黑色（最多隻有一個孩子且為紅色，因為替代節點最多隻有一個孩子），delNode有一個孩子時，刪除delNode節點，然後把孩子節點的顏色改成黑色，也可直接結束
第三種情況： delNode為黑色，且沒有孩子時，有下面幾種情況（兄弟節點叫b(brother)，父親節點叫p(parent)）（下面是cur是parent的左孩子的情形，右孩子的情形和它類似，不介紹）：
情況1： p為黑，b為紅，兩個孩子存在且一定為黑
操作： 對p進行左單旋，然後將p的顏色改成紅，b的顏色改成黑
分析： 調整之前抽象三角形的黑色節點都是a，因為cur下面有一個節點要被刪除，所以cur下面少瞭一個黑色節點，也就是p的左邊少瞭一個黑色節點，調整後b兩邊的黑色節點數不變，cur下面黑色節點數還是少瞭一個，但是它的兄弟是黑色節點，後面可以通過對cur進行檢索，使用其它情況解決這個問題。
抽象圖：
情況2： p為紅，b為黑，b的兩個孩子存在且一定為黑
操作： 把p的顏色改成黑，b的顏色改成紅
分析： 調整前，p左邊少瞭一個黑色的節點，調整後，p的左邊補上瞭一個黑色節點，且p的右邊的黑色節點數不變，這裡可以結束
抽象圖：
情況3： p為黑色，且b為黑色，b的兩個孩子為黑
操作： 把b的顏色改為紅
分析： 調整之前，p左邊是缺少一個黑色節點的，調整後，兩邊黑色節點數相同，但是此時p的右邊也少瞭一個黑色節點，此時p的父親g，g的右邊是比左邊多一個黑色節點的，所以需要迭代向上調整，把cur變成p，繼續對cur進行檢索
抽象圖：
情況4： p為任意顏色，b的顏色為黑，b的右孩子為紅色
操作： 對p進行左單旋，然後交換p和b的顏色，並把b的顏色改成黑
分析： 調整前，a和b的黑色節點數都是x，c,d,e的黑色節點個數為x+1，也就是p的左邊少瞭一個黑色的節點，調整後，p兩邊的黑色節點都是x+1，b兩邊的黑色節點都是x+2，整體都調整好瞭，所以這裡可以結束
抽象圖：
情況5： p為任意顏色，b的顏色為黑，b的左孩子為紅色
操作： 先對b進行右單旋，然後把b改紅，bL改黑，然後對p進行左單旋，然後交換p和b的顏色，並把b的顏色改成黑（情況4）
分析： 和情況四其實是一樣的，情況4的b和bR是直線，這裡是折線，要通過右單旋變成直線，然後就轉為情況4
抽象圖：
總結： 刪除就是以上幾種情況，一般是左邊少一個黑色節點，就靠右邊補一個，結束，或者右邊減少一個，然後兩邊整體少一個，對父親節點進行檢索。
🍯刪除代碼實現
代碼實現如下：
bool Erase(const K& key)
{
// 如果樹為空，刪除失敗
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
Node* delNode = nullptr;
Node* delNodeParent = nullptr;
while (cur)
{
// 小於往左邊走
if (key < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到瞭，開始刪除
// 1.左右子樹都為空 直接刪除 可以歸類為左為空
// 2.左右子樹隻有一邊為空 左為空，父親指向我的右，右為空，父親指向我的左
// 3.左右子樹都不為空 取左子樹最大的節點或右子樹最小的節點和要刪除的節點交換，然後再刪除
if (cur->_left == nullptr)
{
// 要刪除節點為根節點時，直接把右子樹的根節點賦值給——root
// 根節點的話會導致parent為nullptr
if (_root == cur)
{
_root = _root->_right;
if (_root)
{
_root->_parent = nullptr;
_root->_color = BLACK;
}
return true;
}
else
{
delNode = cur;
delNodeParent = parent;
}
}
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
if (_root)
{
_root->_parent = nullptr;
_root->_color = BLACK;
}
return true;
}
else
{
delNode = cur;
delNodeParent = parent;
}
}
else
{
// 找右子樹中最小的節點
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 去右子樹找
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//swap(cur->_key, rightMin->_key);
// 替代刪除
cur->_kv = rightMin->_kv;
delNode = rightMin;
delNodeParent = rightMinParent;
}
break;
}
}
// 沒找到
if (cur == nullptr)
return false;
// 1.替代節點為紅，直接刪除（看上面）
// 2.替代節點為黑（隻能有一個孩子或兩個孩子）
// i)替代節點有一個孩子不為空（該孩子一定為紅）,把孩子的顏色改成黑
// ii)替代節點的兩個孩子都為空
cur = delNode;
parent = delNodeParent;
if (cur->_color == BLACK)
{
if (cur->_left)// 左孩子不為空
{
cur->_left->_color = BLACK;
}
else if (cur->_right)
{
cur->_right->_color = BLACK;
}
else// 替代節點的兩個孩子都為空
{
while (parent)
{
// cur是parent的左
if (cur == parent->_left)
{
Node* brother = parent->_right;
// p為黑
if (parent->_color == BLACK)
{
Node* bL = brother->_left;
Node* bR = brother->_right;
// SL和SR一定存在且為黑
if (brother->_color == RED)// b為紅，SL和SR都為黑 b的顏色改黑，p的顏色改紅 情況a
{
RotateL(parent);
brother->_color = BLACK;
parent->_color = RED;
// 沒有結束，還要對cur進行檢索
}
else if(bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b為黑，孩子存在
{
// 且孩子也為黑 把brother改成紅色，迭代 GP比GU小1 情況b
brother->_color = RED;
cur = parent;
parent = parent->_parent;
}
// bL存在為紅，bR不存在或bR為黑 情況e 右旋後變色轉為情況d
else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK)))
{
RotateR(brother);
bL->_color = BLACK;
brother->_color = RED;
}
else if (bR && bR->_color == RED) // 右孩子為紅，進行一個左旋，然後把右孩子的顏色改成黑色 情況d
{
RotateL(parent);
swap(brother->_color, parent->_color);
bR->_color = BLACK;
break;
}
else
{
// cur p b 都是黑，且b無孩子，迭代更新
// parent是紅就結束
brother->_color = RED;
cur = parent;
parent = parent->_parent;
}
}
// p為紅 b一定為黑
else
{
Node* bL = brother->_left;
Node* bR = brother->_right;
if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全為黑 情況c p變黑，b變紅 結束
{
brother->_color = RED;
parent->_color = BLACK;
break;
}
// bL存在為紅，bR不存在或bR為黑 情況e 右旋後變色轉為情況d
else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK)))
{
RotateR(brother);
bL->_color = BLACK;
brother->_color = RED;
}
else if (bR && bR->_color == RED) // 右孩子為紅，進行一個左旋，然後把右孩子的顏色改成黑色 情況d
{
RotateL(parent);
//swap(brother->_color, parent->_color);
brother->_color = parent->_color;
parent->_color = BLACK;
bR->_color = BLACK;
break;
}
else// cur 為黑，p為紅，b為黑 調整顏色，結束
{
parent->_color = BLACK;
brother->_color = RED;
break;
}
}
}
else
{
Node* brother = parent->_left;
// p為黑
if (parent->_color == BLACK)
{
Node* bL = brother->_left;
Node* bR = brother->_right;
// SL和SR一定存在且為黑
if (brother->_color == RED)// b為紅，SL和SR都為黑 b的顏色改黑，p的顏色改紅 情況a
{
RotateR(parent);
brother->_color = BLACK;
parent->_color = RED;
// 沒有結束，還要對cur進行檢索
}
else if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b為黑，孩子存在
{
// 且孩子也為黑 把brother改成紅色，迭代 GP比GU小1 情況b
brother->_color = RED;
cur = parent;
parent = parent->_parent;
}
// 右孩子存在且為紅，但左孩子不存在或為黑 情況e 右旋後變色轉為情況d
else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK)))
{
RotateL(brother);
brother->_color = RED;
bR->_color = BLACK;
}
else if (bL && bL->_color == RED) // 左孩子為紅，進行一個右旋，然後把左孩子的顏色改成黑色 情況d
{
RotateR(parent);
swap(brother->_color, parent->_color);
bL->_color = BLACK;
break;
}
else
{
// cur p b 都是黑，且b無孩子，迭代更新
// if (parent == _root) // p是根節點，把b變紅 否則迭代
brother->_color = RED;
cur = parent;
parent = parent->_parent;
}
}
// p為紅 b一定為黑
else
{
Node* bL = brother->_left;
Node* bR = brother->_right;
if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全為黑 情況c p變黑，b變紅 結束
{
brother->_color = RED;
parent->_color = BLACK;
break;
}
// 右孩子存在且為紅，但左孩子不存在或為黑 情況e 右旋後變色轉為情況d
else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK)))
{
RotateL(brother);
brother->_color = RED;
bR->_color = BLACK;
}
else if (bL && bL->_color == RED) // 左孩子為紅，進行一個右旋，然後把左孩子的顏色改成黑色 情況d
{
RotateR(parent);
// swap(brother->_color, parent->_color);
brother->_color = parent->_color;
parent->_color = BLACK;
bL->_color = BLACK;
break;
}
else// cur 為黑，p為紅，b為黑 調整顏色，結束
{
parent->_color = BLACK;
brother->_color = RED;
break;
}
}
}
}
}
}
delNodeParent = delNode->_parent;
// 刪除
if (delNode->_left == nullptr)
{
if (delNodeParent->_left == delNode)
delNodeParent->_left = delNode->_right;
else
delNodeParent->_right = delNode->_right;
if (delNode->_right)// 右不為空，就讓右節點的父指針指向delNodeParent
delNode->_right->_parent = delNodeParent;
}
else
{
if (delNodeParent->_left == delNode)
delNodeParent->_left = delNode->_left;
else
delNodeParent->_right = delNode->_left;
if (delNode->_left)// 右不為空，就讓右節點的父指針指向delNodeParent
delNode->_left->_parent = delNodeParent;
}
delete delNode;
delNode = nullptr;
return true;
}
🌲紅黑樹的查找
這裡比較簡單，直接上代碼：
bool Find(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
// 小於往左走
if (key < cur->_kv.first)
{
cur = cur->_left;
}
// 大於往右走
else if (key > cur->_kv.first)
{
cur = cur->_right;
}
else
{
// 找到瞭
return true;
}
}
return false;
}
🌲紅黑樹的驗證
這裡通過遞歸計算出每條路徑的節點個數來進行比較，同時驗證其他的性質是否符合，從而驗證是否紅黑樹：
bool IsValidRBTree()
{
// 空樹也是紅黑樹
if (_root == nullptr)
return true;
// 判斷根節點的顏色是否為黑色
if (_root->_color != BLACK)
{
cout << "違反紅黑樹的根節點為黑色的規則" << endl;
return false;
}
// 計算出任意一條路徑的黑色節點個數
size_t blackCount = 0;
Node* cur = _root;
while (cur)
{
if (cur->_color == BLACK)
++blackCount;
cur = cur->_left;
}
// 檢測每條路徑黑節點個數是否相同 第二個參數記錄路徑中黑節點的個數
return _IsValidRBTree(_root, 0, blackCount);
}
bool _IsValidRBTree(Node* root, size_t k, size_t blackCount)
{
// 走到空就判斷該條路徑的黑節點是否等於blackCount
if (root == nullptr)
{
if (k != blackCount)
{
cout << "違反每條路徑黑節點個數相同的規則" << endl;
return false;
}
return true;
}
if (root->_color == BLACK)
++k;
// 判斷是否出現瞭連續兩個紅色節點
Node* parent = root->_parent;
if (parent && root->_color == RED && parent->_color == RED)
{
cout << "違反瞭不能出現連續兩個紅色節點的規則" << endl;
return false;
}
return _IsValidRBTree(root->_left, k, blackCount)
&& _IsValidRBTree(root->_right, k, blackCount);
}
實例演示：
void TestRBTree()
{
//srand((size_t)time(nullptr));
RBTree<int, int> rbt;
// int a[] = { 1,2,3,4,5,6,7,8,9,10,5,7,8,11,12,13 };
// int a[] = { 16,3,7,11,9,26,18,14,15 };
// int a[] = { 4,2,6,1,3,5,15,7,16,14 };
// int a[] = { 10,9,8,7,6,5,4,3,2,1 };
vector<int> a;
for (size_t i = 0; i < 13; ++i)
{
// a.push_back(rand());
a.push_back(i);
}
//int a[] = { 4,2,6,7,3,5 };
/*vector<int> v;
v.reserve(100000);
for (size_t i = 1; i <= v.capacity(); ++i)
{
v.push_back(i);
}*/
for (auto e : a)
{
int begin = clock();
rbt.Insert(make_pair(e, e));
int end = clock();
cout << "插入數據 " << e << " 後：" << "樹的高度：" << rbt.Height() << " 是否為紅黑樹：" << rbt.IsValidRBTree();
cout << " 用時：" << end - begin << "ms" << endl;
}
cout << "-------------------------------------------------------" << endl;
for (auto e : a)
{
int begin = clock();
rbt.Erase(e);
int end = clock();
cout << "刪除數據 " << e << " 後：" << "樹的高度：" << rbt.Height() << " 是否為紅黑樹：" << rbt.IsValidRBTree();
cout << " 用時：" << end - begin << "ms" << endl;
}
// cout << rbt.IsValidRBTree() << endl;
// rbt.InOrder();
}
代碼運行結果如下：
🌏AVL樹和紅黑樹的比較
| AVL樹 | 紅黑樹 | |
|---|---|---|
| 如何控制平衡 | 通過條件平衡因子，子樹左右高度差不超過1 | 用過顏色控制，使得最長路徑不超出最短路徑的長度的兩倍 |
| 增刪查改的時間復雜度 | 可以穩定在O(logN) | 基本是O(logN)，極端情況下是O(log2N) |
總結： AVL樹是嚴格意義上的平衡，紅黑樹是相對的平衡，兩者都很高效，但後者用的更多，因為它旋轉更是，實現相對簡單，付出的代價少一點。
🌐總結
二叉搜索樹的內容就介紹到這，接下來我會給大傢介紹map和set兩個容器，它們的底層就是紅黑樹，我會用紅黑樹給大傢模擬實現它們。喜歡的話，歡迎點贊支持和關註~
到此這篇關於C++數據結構紅黑樹全面分析的文章就介紹到這瞭,更多相關C++ 紅黑樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！