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