C++數(shù)據(jù)結(jié)構(gòu)紅黑樹全面分析
??博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
??概念和性質(zhì)
紅黑樹的概念： 紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。它是通過控制節(jié)點顏色的方式來控制這棵樹的相對平衡，保證了沒有一條路徑會比其它路徑長出兩倍。
紅黑樹的性質(zhì)：
- 結(jié)點是紅色或黑色。
- 根結(jié)點是黑色。
- 所有葉子都是黑色。（葉子是空結(jié)點）
- 每個紅色結(jié)點的兩個子結(jié)點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點）
- 從任一節(jié)結(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點
上面的五個性質(zhì)還可以用更通俗的語言描述為三句話：
- 根節(jié)點是黑色的
- 沒有連續(xù)的紅節(jié)點
- 每條路徑的黑節(jié)點數(shù)目相同（每條路徑指的是從根節(jié)點到黑色的空節(jié)點）
思考： 為什么紅黑樹中最長路徑的長度不會超過最短路徑節(jié)點個數(shù)的兩倍？
最長路徑： 該條路徑上節(jié)點分布是一紅一黑
最短路徑： 該條路徑上節(jié)點分布是全黑
假設(shè)每條路徑黑色節(jié)點數(shù)為N，則最長路徑為2N，最短路徑為N，所以這樣就推出紅黑樹中最長路徑的長度不會超過最短路徑節(jié)點個數(shù)的兩倍。
??紅黑樹的實現(xiàn)
??紅黑樹節(jié)點定義
這里也是一個三叉鏈，其中每個節(jié)點包含顏色的元素在里面：
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)
{}
};??紅黑樹結(jié)構(gòu)定義
里面只包含一個根節(jié)點的成員變量，和前面兩棵樹的結(jié)構(gòu)定義沒有什么大的區(qū)別，區(qū)別在于節(jié)點的定義：
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
??紅黑樹的插入
??方法概述
第一步： 我們先按照二叉搜索樹樹插入節(jié)點的方式，插入節(jié)點
第二步： 為了不破壞紅黑樹的規(guī)則，我們插入節(jié)點后要對紅黑樹進行相應的調(diào)整
思考： 我們插入節(jié)點應該默認插入紅色節(jié)點好還是黑色節(jié)點好呢？ 答案是紅色節(jié)點。為什么呢？我們要考慮哪種方式對紅黑樹的破壞性更大一點。如果是黑色，此時黑導致該條路徑比其它路徑上黑色節(jié)點數(shù)都多一個，這樣下來調(diào)整紅黑樹的步驟代價似乎會有點大；如果是紅色，不會破壞規(guī)則5，只是破壞規(guī)則4，可能會出現(xiàn)連續(xù)的紅色節(jié)點，這樣我們只需要調(diào)整該節(jié)點及其附近節(jié)點的顏色即可，代價沒有前一種方式大，所以我們選擇第二種方式。
??調(diào)整節(jié)點顏色
第一種情況： 如果插入節(jié)點的父親是黑色節(jié)點，那么可以直接結(jié)束，不需要繼續(xù)調(diào)整了
第二種情況： 如果插入節(jié)點為的父親為紅色節(jié)點，就需要進行相應的調(diào)整 下面討論父親節(jié)點是祖父節(jié)點的左孩子的幾種情形（是右孩子的情形和這個類型，大家可以自己推演一下，這里我們把父親節(jié)點叫做p(parent)，祖父叫g(shù)(grandfather)，叔叔節(jié)點叫u(uncle)）：
情況1： p為紅色（g肯定是存在的且為黑），u存在且為紅
操作： 把p和u改成黑，g改成紅，如果g為根節(jié)點就把g的顏色變成黑然后結(jié)束，如果g不為根節(jié)點，且g的父親為黑色也節(jié)數(shù)，為紅色就需要迭代向上調(diào)整，判斷此時處于何種情況 具像圖：
如果g的父親為紅，就迭代向上調(diào)整：cur = grandfather,grandfather = grandfather->parent
抽象圖：抽象圖中cur可能是新插入的節(jié)點，也可能是迭代調(diào)整上來的節(jié)點，這里g這棵子樹每條路徑黑色節(jié)點數(shù)是相同的，且調(diào)整后g這棵子樹的每條路徑黑色數(shù)相同且和之前一樣。cur是parent的左孩子和右孩子是一樣的，因為這里都是對顏色進行控制，和方向無關(guān)。
情況2： p為紅色（g肯定是存在的且為黑），u不存在
操作： cur為parent的左孩子時，對g進行右單旋，然后將p的顏色改黑，g的顏色改紅；cur為parent的右孩子時，先對p進行左單旋，然后對g進行右單旋，然后將cur的顏色改黑，g的顏色改紅 具象圖：此時cur一定為新增節(jié)點，因為g的右子樹沒有黑節(jié)點，所以cur的下面也不可能有黑節(jié)點 cur為parent的左孩子時 一條直線，此時進行右單旋
cur為parent的左孩子時 一條折線，此時進行左右雙旋
上面的第二種情況可以先進行左單旋，然后交換cur和p，把折線變?yōu)橹本€，最后都執(zhí)行直線的情況。
情況3： p為紅色（g肯定是存在的且為黑），u存在且為黑
操作： 如果cur為parent的左孩子，對g進行右單旋，然后將p的顏色改為黑，g的顏色改為紅；如果cur為parent的右孩子，先對p進行左單旋，對g進行右單旋，然后將cur的顏色改為黑，g的顏色改為紅
解釋： 假設(shè)此時a和b中黑色節(jié)點數(shù)為a，c的黑色節(jié)點數(shù)也一定為a，d和e的黑色節(jié)點數(shù)就是a-1，調(diào)整后cur和g的抽象圖的黑色節(jié)點都是a，整體相等。 抽象圖：此時cur一定為調(diào)整上來的節(jié)點，因為如果是新增節(jié)點的話，那么原來g這棵子樹左右黑色節(jié)點數(shù)目不等，所以cur一定是調(diào)整上來的節(jié)點。 cur為parent的左孩子 一條直線，進行右單旋即可
cur為parent的右孩子 一條折線，此時進行左右雙旋
和情況2一樣，上面的第二種情況可以先進行左單旋，然后交換cur和p，把折線變?yōu)橹本€，最后都執(zhí)行直線的情況。
總結(jié)： 上面就是p是g的左孩子的所有情形，為g的右孩子是與這個類似。還有注意的是根節(jié)點最后一定要改為黑色。
??插入代碼實現(xiàn)
旋轉(zhuǎn)代碼如下： 這里就是上一篇博客的旋轉(zhuǎn)代碼，具體如下
// 左單旋
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;
}
}插入代碼實現(xiàn)如下：
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv, BLACK);// 根節(jié)點默認給黑
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);
}
// 節(jié)點默認給紅節(jié)點，帶來的影響更小
// 給黑節(jié)點的話會影響 每條路徑的黑節(jié)點相同這條規(guī)則
cur = new Node(kv);
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 調(diào)整顏色
// 情況一：p是紅，g是黑，u存在且為紅
// 調(diào)整后的幾種情況：
// 1.如果g為根節(jié)點，把g的顏色改成黑，結(jié)束；
// 2.如果g不為根節(jié)點，
// a.g的父節(jié)點為黑，結(jié)束；
// b.g的父節(jié)點為紅，迭代向上調(diào)整,繼續(xù)判斷是哪種情況（一和三）
// cur = grandfather;
// father = cur->father;
// 這里不管cur是在p的左邊還是右邊，都是一樣的，關(guān)心的是顏色而不是位置
// 情況二：p是紅，g是黑，u不存在/u為黑 cur p g 三個是一條直線
// 調(diào)整方法（左邊為例）：1.右單旋 2.把p改成黑，g改成紅
// a. u不存在時，cur必定是新增節(jié)點
// b. u存在時，cur必定是更新上來的節(jié)點
// 情況三：p是紅，g是黑，u不存在/u為黑 cur p g 三個是一條折線
// 調(diào)整方法（左邊為例）：1.p左單旋 2.g右單旋 3.把cur改成黑，g改成紅
// a. u不存在時，cur必定是新增節(jié)點
// b. u存在時，cur必定是更新上來的節(jié)點
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
// 左邊
if (grandfather->_left == parent)
{
// 紅黑色的條件關(guān)鍵看叔叔
Node* uncle = grandfather->_right;
// u存在且為紅
if (uncle && uncle->_color == RED)
{
// 調(diào)整 p和u改成黑，g改成紅
parent->_color = uncle->_color = BLACK;
grandfather->_color = RED;
// 迭代 向上調(diào)整
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;
// 迭代 向上調(diào)整
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);
}??紅黑樹的刪除
??方法概述
第一步： 先按照二叉搜索樹刪除節(jié)點的方式找到要刪除節(jié)點（也可能是替代節(jié)點）
第二步： 然后為了不破壞紅黑樹的幾條規(guī)則，要對節(jié)點的顏色進行相應地調(diào)整
??調(diào)整顏色
第一種情況： 刪除節(jié)點（也可能是替代節(jié)點）（之后都叫delNode），如果該節(jié)點為紅色，則直接刪除退出即可，delNode沒找到也可以直接退出
第二種情況： delNode為黑色（最多只有一個孩子且為紅色，因為替代節(jié)點最多只有一個孩子），delNode有一個孩子時，刪除delNode節(jié)點，然后把孩子節(jié)點的顏色改成黑色，也可直接結(jié)束
第三種情況： delNode為黑色，且沒有孩子時，有下面幾種情況（兄弟節(jié)點叫b(brother)，父親節(jié)點叫p(parent)）（下面是cur是parent的左孩子的情形，右孩子的情形和它類似，不介紹）：
情況1： p為黑，b為紅，兩個孩子存在且一定為黑
操作： 對p進行左單旋，然后將p的顏色改成紅，b的顏色改成黑
分析： 調(diào)整之前抽象三角形的黑色節(jié)點都是a，因為cur下面有一個節(jié)點要被刪除，所以cur下面少了一個黑色節(jié)點，也就是p的左邊少了一個黑色節(jié)點，調(diào)整后b兩邊的黑色節(jié)點數(shù)不變，cur下面黑色節(jié)點數(shù)還是少了一個，但是它的兄弟是黑色節(jié)點，后面可以通過對cur進行檢索，使用其它情況解決這個問題。
抽象圖：
情況2： p為紅，b為黑，b的兩個孩子存在且一定為黑
操作： 把p的顏色改成黑，b的顏色改成紅
分析： 調(diào)整前，p左邊少了一個黑色的節(jié)點，調(diào)整后，p的左邊補上了一個黑色節(jié)點，且p的右邊的黑色節(jié)點數(shù)不變，這里可以結(jié)束
抽象圖：
情況3： p為黑色，且b為黑色，b的兩個孩子為黑
操作： 把b的顏色改為紅
分析： 調(diào)整之前，p左邊是缺少一個黑色節(jié)點的，調(diào)整后，兩邊黑色節(jié)點數(shù)相同，但是此時p的右邊也少了一個黑色節(jié)點，此時p的父親g，g的右邊是比左邊多一個黑色節(jié)點的，所以需要迭代向上調(diào)整，把cur變成p，繼續(xù)對cur進行檢索
抽象圖：
情況4： p為任意顏色，b的顏色為黑，b的右孩子為紅色
操作： 對p進行左單旋，然后交換p和b的顏色，并把b的顏色改成黑
分析： 調(diào)整前，a和b的黑色節(jié)點數(shù)都是x，c,d,e的黑色節(jié)點個數(shù)為x+1，也就是p的左邊少了一個黑色的節(jié)點，調(diào)整后，p兩邊的黑色節(jié)點都是x+1，b兩邊的黑色節(jié)點都是x+2，整體都調(diào)整好了，所以這里可以結(jié)束
抽象圖：
情況5： p為任意顏色，b的顏色為黑，b的左孩子為紅色
操作： 先對b進行右單旋，然后把b改紅，bL改黑，然后對p進行左單旋，然后交換p和b的顏色，并把b的顏色改成黑（情況4）
分析： 和情況四其實是一樣的，情況4的b和bR是直線，這里是折線，要通過右單旋變成直線，然后就轉(zhuǎn)為情況4
抽象圖：
總結(jié)： 刪除就是以上幾種情況，一般是左邊少一個黑色節(jié)點，就靠右邊補一個，結(jié)束，或者右邊減少一個，然后兩邊整體少一個，對父親節(jié)點進行檢索。
??刪除代碼實現(xiàn)
代碼實現(xiàn)如下：
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.左右子樹都不為空 取左子樹最大的節(jié)點或右子樹最小的節(jié)點和要刪除的節(jié)點交換，然后再刪除
if (cur->_left == nullptr)
{
// 要刪除節(jié)點為根節(jié)點時，直接把右子樹的根節(jié)點賦值給——root
// 根節(jié)點的話會導致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
{
// 找右子樹中最小的節(jié)點
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.替代節(jié)點為紅，直接刪除（看上面）
// 2.替代節(jié)點為黑（只能有一個孩子或兩個孩子）
// i)替代節(jié)點有一個孩子不為空（該孩子一定為紅）,把孩子的顏色改成黑
// ii)替代節(jié)點的兩個孩子都為空
cur = delNode;
parent = delNodeParent;
if (cur->_color == BLACK)
{
if (cur->_left)// 左孩子不為空
{
cur->_left->_color = BLACK;
}
else if (cur->_right)
{
cur->_right->_color = BLACK;
}
else// 替代節(jié)點的兩個孩子都為空
{
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;
// 沒有結(jié)束，還要對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 右旋后變色轉(zhuǎn)為情況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是紅就結(jié)束
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變紅 結(jié)束
{
brother->_color = RED;
parent->_color = BLACK;
break;
}
// bL存在為紅，bR不存在或bR為黑 情況e 右旋后變色轉(zhuǎn)為情況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為黑 調(diào)整顏色，結(jié)束
{
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;
// 沒有結(jié)束，還要對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 右旋后變色轉(zhuǎn)為情況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是根節(jié)點，把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變紅 結(jié)束
{
brother->_color = RED;
parent->_color = BLACK;
break;
}
// 右孩子存在且為紅，但左孩子不存在或為黑 情況e 右旋后變色轉(zhuǎn)為情況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為黑 調(diào)整顏色，結(jié)束
{
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)// 右不為空，就讓右節(jié)點的父指針指向delNodeParent
delNode->_right->_parent = delNodeParent;
}
else
{
if (delNodeParent->_left == delNode)
delNodeParent->_left = delNode->_left;
else
delNodeParent->_right = delNode->_left;
if (delNode->_left)// 右不為空，就讓右節(jié)點的父指針指向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;
}??紅黑樹的驗證
這里通過遞歸計算出每條路徑的節(jié)點個數(shù)來進行比較，同時驗證其他的性質(zhì)是否符合，從而驗證是否紅黑樹：
bool IsValidRBTree()
{
// 空樹也是紅黑樹
if (_root == nullptr)
return true;
// 判斷根節(jié)點的顏色是否為黑色
if (_root->_color != BLACK)
{
cout << "違反紅黑樹的根節(jié)點為黑色的規(guī)則" << endl;
return false;
}
// 計算出任意一條路徑的黑色節(jié)點個數(shù)
size_t blackCount = 0;
Node* cur = _root;
while (cur)
{
if (cur->_color == BLACK)
++blackCount;
cur = cur->_left;
}
// 檢測每條路徑黑節(jié)點個數(shù)是否相同 第二個參數(shù)記錄路徑中黑節(jié)點的個數(shù)
return _IsValidRBTree(_root, 0, blackCount);
}
bool _IsValidRBTree(Node* root, size_t k, size_t blackCount)
{
// 走到空就判斷該條路徑的黑節(jié)點是否等于blackCount
if (root == nullptr)
{
if (k != blackCount)
{
cout << "違反每條路徑黑節(jié)點個數(shù)相同的規(guī)則" << endl;
return false;
}
return true;
}
if (root->_color == BLACK)
++k;
// 判斷是否出現(xiàn)了連續(xù)兩個紅色節(jié)點
Node* parent = root->_parent;
if (parent && root->_color == RED && parent->_color == RED)
{
cout << "違反了不能出現(xiàn)連續(xù)兩個紅色節(jié)點的規(guī)則" << 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 << "插入數(shù)據(jù) " << 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 << "刪除數(shù)據(jù) " << e << " 后：" << "樹的高度：" << rbt.Height() << " 是否為紅黑樹：" << rbt.IsValidRBTree();
cout << " 用時：" << end - begin << "ms" << endl;
}
// cout << rbt.IsValidRBTree() << endl;
// rbt.InOrder();
}代碼運行結(jié)果如下：
??AVL樹和紅黑樹的比較
| AVL樹 | 紅黑樹 | |
|---|---|---|
| 如何控制平衡 | 通過條件平衡因子，子樹左右高度差不超過1 | 用過顏色控制，使得最長路徑不超出最短路徑的長度的兩倍 |
| 增刪查改的時間復雜度 | 可以穩(wěn)定在O(logN) | 基本是O(logN)，極端情況下是O(log2N) |
總結(jié)： AVL樹是嚴格意義上的平衡，紅黑樹是相對的平衡，兩者都很高效，但后者用的更多，因為它旋轉(zhuǎn)更是，實現(xiàn)相對簡單，付出的代價少一點。
??總結(jié)
二叉搜索樹的內(nèi)容就介紹到這，接下來我會給大家介紹map和set兩個容器，它們的底層就是紅黑樹，我會用紅黑樹給大家模擬實現(xiàn)它們。喜歡的話，歡迎點贊支持和關(guān)注~
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)紅黑樹全面分析的文章就介紹到這了,更多相關(guān)C++ 紅黑樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了講解C++中的枚舉類型以及聲明新類型的方法,是C預言入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
在C語言中,rand()函數(shù)可以用來產(chǎn)生隨機數(shù)，但是這不是真真意義上的隨機數(shù)，是一個偽隨機數(shù)，這篇文章主要介紹了使用c語言生成隨機數(shù)的示例,需要的朋友可以參考下2014-03-03
內(nèi)存泄漏會導致當前應用程序消耗更多的內(nèi)存，使得其他應用程序可用的內(nèi)存更少了，那么為什么會內(nèi)存泄漏，我們應該怎樣應對內(nèi)存泄漏，所以接下來就給大家詳細介紹一下C++內(nèi)存泄漏原因分析與應對方法,需要的朋友可以參考下2023-07-07
本篇文章是對C++中常見關(guān)鍵字的含義進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家介紹了c++?對象在棧上還是在堆上問題分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
本篇文章是對c++中的變量類型進行了詳細的分析介紹。需要的朋友參考下2013-05-05
字符串輸入是C語言編程中非常重要的部分,其中scanf函數(shù)是一種廣泛使用的輸入字符串的方法,下面這篇文章主要給大家介紹了關(guān)于C語言輸入一個字符串的方法有哪些的相關(guān)資料,需要的朋友可以參考下2023-06-06
這篇文章主要介紹了C/C++ 的*和&的相關(guān)知識，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-11-11
所謂“位域”是把一個字節(jié)中的二進位劃分為幾個不同的區(qū)域， 并說明每個區(qū)域的位數(shù)。每個域有一個域名，允許在程序中按域名進行操作。 這樣就可以把幾個不同的對象用一個字節(jié)的二進制位域來表示。下面這篇文章就給大家介紹下關(guān)于C語言中位域的使用與注意事項。2016-12-12
C++圖形界面開發(fā)Qt教程:嵌套圓環(huán)示例
這篇文章主要介紹了C++實現(xiàn)圖形界面開發(fā)Qt教程,涉及坐標函數(shù)的應用及圖形界面程序設(shè)計,需要的朋友可以參考下,希望能給你帶來幫助2021-08-08