??歡迎來到數(shù)據(jù)結(jié)構(gòu)專欄~~手撕紅黑樹
- (???(??? )??,我是Scort
- 目前狀態(tài)：大三非科班啃C++中
- ??博客主頁：張小姐的貓~江湖背景
- 快上車??，握好方向盤跟我有一起打天下嘞！
- 送給自己的一句雞湯??：
- ??真正的大師永遠(yuǎn)懷著一顆學(xué)徒的心
- 作者水平很有限，如果發(fā)現(xiàn)錯(cuò)誤，可在評(píng)論區(qū)指正，感謝??
- ????歡迎持續(xù)關(guān)注！
一. 紅黑樹的概念??
紅黑樹也是一種二叉搜索樹，但是每個(gè)節(jié)點(diǎn)都存儲(chǔ)了一個(gè)顏色，該顏色可以為黑可以為紅，因此也叫紅黑樹
紅黑樹和AVL樹的區(qū)別就是：紅黑樹是近似平衡，但不是完全平衡，沒有和AVL樹一樣 的通過平衡因子來控制高度差，而是通過每條路徑上對(duì)紅黑節(jié)點(diǎn)的控制，來達(dá)到確保最長(zhǎng)路徑長(zhǎng)度不超過最短路徑長(zhǎng)度的 2 倍。
二. 五大特性
- 根節(jié)點(diǎn)一定為黑色
- 每個(gè)節(jié)點(diǎn)只能是 紅或黑
- 節(jié)點(diǎn)為紅色，則該節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色（也就是樹中沒有連續(xù)的紅色節(jié)點(diǎn)）
- 對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉子結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)（每條路徑的黑色節(jié)點(diǎn)相等）
- 每個(gè)葉子結(jié)點(diǎn)都是黑色（此處的葉子節(jié)點(diǎn)指的是空節(jié)點(diǎn)：
NIL節(jié)點(diǎn)）
如果是空樹，剛好是空節(jié)點(diǎn)為黑色，也符合第一條規(guī)則
那么問題來了，僅僅依靠這五大特性是如何確保最長(zhǎng)路徑長(zhǎng)度 <= 最短路徑長(zhǎng)度的 2 倍？
根據(jù)紅黑樹的性質(zhì)3可以得出，紅黑樹當(dāng)中不會(huì)出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)，而根據(jù)性質(zhì)4又可以得出，從某一結(jié)點(diǎn)到其后代葉子結(jié)點(diǎn)的所有路徑上包含的黑色結(jié)點(diǎn)的數(shù)目是相同的
所以我們不妨假設(shè)極端場(chǎng)景，最短的路徑無非就是全黑的情況了，假設(shè)此時(shí)有 n 個(gè)節(jié)點(diǎn)，長(zhǎng)度就為 n
而最長(zhǎng)路徑就是：一紅一黑排列的，如果有 n 個(gè)黑色節(jié)點(diǎn)，那么紅色節(jié)點(diǎn)數(shù)目與黑色相同，則長(zhǎng)度為 2n，所以不超過兩倍！
三. 節(jié)點(diǎn)的定義
cv工程師登場(chǎng)！此處我們還是定義成三叉鏈，只不過把平衡因子替換成了節(jié)點(diǎn)顏色，因?yàn)楣?jié)點(diǎn)的顏色就兩種，直接枚舉就好了
//枚舉顏色
enum Colour
{
RED,
Black
};
定義的節(jié)點(diǎn)如下：
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//三叉鏈
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;//存儲(chǔ)鍵值對(duì)
Colour _col;//節(jié)點(diǎn)顏色
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
此處有個(gè)問題：為什么構(gòu)造結(jié)點(diǎn)時(shí)，默認(rèn)將結(jié)點(diǎn)的顏色設(shè)置為紅色？
此處我們知道插入黑色的節(jié)點(diǎn)是一定違反了性質(zhì)4；某條路徑的黑色節(jié)點(diǎn)一定會(huì)增加一個(gè)，那為了維護(hù)結(jié)構(gòu)，我們豈不是要在其他的路徑是不是也要增加一個(gè)呢？
但此時(shí)如果新增的是一個(gè)紅色的節(jié)點(diǎn)呢；如果根節(jié)點(diǎn)為紅色，那么又會(huì)破壞性質(zhì) 3 出現(xiàn)了連續(xù)的紅色節(jié)點(diǎn)，但是如果根節(jié)點(diǎn)為黑色，就不需要進(jìn)行調(diào)整。 也就是說新增red節(jié)點(diǎn)不一定會(huì)破壞結(jié)構(gòu)，但新增Black節(jié)點(diǎn)就一定會(huì)破壞。
四. 紅黑樹插入
此處插入的前半部分和AVL樹的插入一樣：
- 按二叉搜索樹的插入方法，找到待插入位置
- 將待插入結(jié)點(diǎn)插入到樹中
- 若插入結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色的，則需要對(duì)紅黑樹進(jìn)行調(diào)整
紅黑樹的關(guān)鍵就在這第三步中！大有來頭
?模型
我們先給出一個(gè)基本模型：（可以是子樹也可以是一棵完整的樹）
cur ：當(dāng)前節(jié)點(diǎn)
p：parent，父節(jié)點(diǎn)
g：grandfather，祖父節(jié)點(diǎn)
u：uncle，叔叔節(jié)點(diǎn)
a，b，c，d，e：子樹
順便科普一下樹的路徑是從根節(jié)點(diǎn)一路走到空節(jié)點(diǎn)（NIL 節(jié)點(diǎn)）才算一條路徑,而不是走到葉子就停下來了
所以上面這棵樹的有效路徑有9條，而不是4條
??情況一：u 存在且為紅
cur 為紅，p 為紅，g 為黑， u 存在且為紅
首先我們知道紅黑樹的關(guān)鍵是看叔叔uncle；節(jié)點(diǎn)的顏色是固定為黑色的；因?yàn)椴荒苡袃蓚€(gè)相同的紅色節(jié)點(diǎn)，所以我們開始調(diào)整！首先將parent變成黑色；又為了不違反性質(zhì)4，所以u(píng)ncle的節(jié)點(diǎn)也要變成黑色；同時(shí)也要將grandparent節(jié)點(diǎn)變紅，不要忘了這可能只是一顆子樹；為了維持每條路徑上黑色節(jié)點(diǎn)的數(shù)量；祖父必須變紅，不然會(huì)多出一個(gè)黑色節(jié)點(diǎn)。
最后不要忘了將祖父當(dāng)成 cur 節(jié)點(diǎn)繼續(xù)向上調(diào)整，直到g是根，最后才將變成黑色！
具體代碼：
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
//關(guān)鍵看叔叔 ~ 判斷叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col = RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle ->_col = Black;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2
{}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle&& uncle->_col = RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = Black;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2
{}
}
}
_root->_col = BLACK;//不管什么，最后根要變黑
return true;
}
??情況二：
??具體情況1??：u不存在
cur 為紅，p 為紅，g 為黑， u 不存在
如果叔叔不存在，那么a/b/c/d/e都是空樹，cur是新增節(jié)點(diǎn)！因?yàn)槭迨宀淮嬖诘脑?，parent下也不可能掛上黑節(jié)點(diǎn)！
此處也違背了性質(zhì)4，所謂單純的變色也無法處理了，那就旋轉(zhuǎn)試試看吧，
祖孫三代在一條直線上偏左，一波右單旋安排，接著根節(jié)點(diǎn)變成 parent 后調(diào)整顏色，父親變黑，祖父變紅，一波操作下來黑節(jié)點(diǎn)數(shù)目沒邊，根節(jié)點(diǎn)也是黑色不用再向上調(diào)整了
??具體情況2??：u存在且為黑
cur 為紅，p 為紅，g 為黑， u 存在且為黑
b和c可以是空樹或者是一個(gè)紅節(jié)點(diǎn)，a可以是根也可以是黑節(jié)點(diǎn)的子樹，下面四種的的任意一種
以下的情況一定是由情況一往上調(diào)整過程中才會(huì)出現(xiàn)的！即這種情況下的cur結(jié)點(diǎn)一定不是新插入的結(jié)點(diǎn)，而是上一次情況一調(diào)整過程中的祖父結(jié)點(diǎn)，如下圖：
此上的情況必定是左邊的的多一個(gè)黑色節(jié)點(diǎn)，如上圖所示， 假設(shè)祖父上面有 x 個(gè)黑節(jié)點(diǎn)，叔叔下有y個(gè)節(jié)點(diǎn)，那么左子樹（含祖父）現(xiàn)在是 x +1 個(gè)，右子樹（含祖父）是 x + 2 + y 個(gè)，很明顯 x + 2 + y > x + 1，因此在插入結(jié)點(diǎn)前就已經(jīng)不滿足要求了，所以說叔叔結(jié)點(diǎn)存在且為黑這種情況，一定是由情況一往上調(diào)整過程中才會(huì)出現(xiàn)的！
此處單純的變色已經(jīng)無法處理，況且還違背了性質(zhì)4；這時(shí)我們需要進(jìn)行旋轉(zhuǎn)+變色處理
如果是祖父、父親、cur 都在同一條直線上，那么只需要單旋即可
??雙旋是怎么樣產(chǎn)生的？
若祖孫三代的關(guān)系是折線（cur、parent、grandfather這三個(gè)結(jié)點(diǎn)為一條折現(xiàn)），則我們需要先進(jìn)行雙旋操作，再進(jìn)行顏色調(diào)整，顏色調(diào)整后這棵被旋轉(zhuǎn)子樹的根是黑色的，因此無需繼續(xù)往上進(jìn)行處理
抽象圖如下：
以上情況的完整代碼：
//如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，則需要對(duì)紅黑樹進(jìn)行操作
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
//關(guān)鍵看叔叔 ~ 判斷叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle ->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// p u
//c
if (cur = parent->_left)
{
RotateR(grandfather);//右旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_right
{
//情況三：左右雙旋 + 變色
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle&& uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// u p
// c
if (cur = parent->_right)
{
RotateL(grandfather);//左單 旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_left
{
//情況三：右左雙旋 + 變色
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
大總結(jié)
無論是情況一還是情況二，cur為紅，p為紅，g為黑這三個(gè)條件是固定的
-
情況一：叔叔存在且為紅：
- 1??單純的變色：p和u變黑，g變紅
- 2??把g繼續(xù)當(dāng)成cur，g不是根繼續(xù)往上處理（繼續(xù)往上處理有可能變成情況2）；g是根就變成黑色
-
情況二：叔叔不存在 or 叔叔存在且為黑
- 1??旋轉(zhuǎn)：具體情況來判斷是什么旋轉(zhuǎn)（祖孫三代是折線關(guān)系就是雙旋，直線就是單旋）
- 2??變色：p變黑， g變紅
五. 驗(yàn)證紅黑樹
還是老套路中序遍歷來驗(yàn)證：
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr)//空樹也是紅黑樹
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
那怎么樣驗(yàn)證它是紅黑樹呢？從五大特性下手！
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根節(jié)點(diǎn)不是黑色" << endl;
return false;
}
// 黑色節(jié)點(diǎn)數(shù)量基準(zhǔn)值
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;
cur = cur->_left;//以最左的路徑進(jìn)行
}
return PrevCheck(_root, 0, benchmark);
}
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}
if (blackNum != benchmark)
{
cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
//檢測(cè)當(dāng)前節(jié)點(diǎn)以及父親
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
return false;
}
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}
六. 紅黑樹的性能
紅黑樹的刪除本節(jié)不做講解，有興趣的可參考：《算法導(dǎo)論》或者《STL源碼剖析》
參考地址
七. 紅黑樹的性能
AVL 樹和紅黑樹都是平衡二叉樹的兩個(gè)老大哥，他們?cè)鰟h查改的時(shí)間復(fù)雜度都O(logN)，到底誰更技高一籌？
其實(shí)在大數(shù)據(jù)的場(chǎng)景下，比如百萬級(jí)量化數(shù)據(jù)，AVL 需要構(gòu)建大約 20 多層，同時(shí)紅黑樹需要構(gòu)建大約 40 多層，畢竟紅黑樹是近似平衡的二叉搜索樹。文章來源：http://www.zghlxwxcb.cn/news/detail-796956.html
但是我們知道 20 和 40 在 CPU 運(yùn)算速度面前并沒有什么差別，雖然 AVL 樹在效率上會(huì)略勝紅黑樹一點(diǎn)點(diǎn)，但是生活中紅黑樹的運(yùn)用卻比 AVL 樹更為廣泛，因?yàn)?AVL 樹的效率是有代價(jià)的，是充分犧牲結(jié)構(gòu)進(jìn)行不斷旋轉(zhuǎn)得到的，而紅黑樹大大降低了旋轉(zhuǎn)次數(shù)會(huì)更安全因此，換來了更優(yōu)的性能文章來源地址http://www.zghlxwxcb.cn/news/detail-796956.html
到了這里，關(guān)于【高階數(shù)據(jù)結(jié)構(gòu)】手撕紅黑樹（超詳細(xì)版本）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-紅黑樹](https://imgs.yssmx.com/Uploads/2024/02/756302-1.png)
