什么是紅黑樹(shù)？本篇文章讓你徹底理解！
1. 紅黑樹(shù)的概念
紅黑樹(shù)，是一種二叉搜索樹(shù)，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。
2. 紅黑樹(shù)的性質(zhì)
2.1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
2.2. 根節(jié)點(diǎn)是黑色的
2.3. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的（不會(huì)出現(xiàn)連在一起的紅色節(jié)點(diǎn)）
2.4. 對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)（在計(jì)算一條路徑中黑色節(jié)點(diǎn)個(gè)數(shù)的時(shí)候要帶上葉子節(jié)點(diǎn)，因?yàn)槿~子節(jié)點(diǎn)也是黑色的，也就是空節(jié)點(diǎn)）。
2.5. 每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn))（為了保證空樹(shù)也是紅黑樹(shù)）
2.6.紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍（紅黑樹(shù)前面的性質(zhì)保證了當(dāng)前的性質(zhì)）
3. 紅黑樹(shù)的實(shí)現(xiàn)
3.1. 帶頭節(jié)點(diǎn)的紅黑樹(shù)
這里我們將紅黑樹(shù)的實(shí)現(xiàn)給為帶頭的紅黑樹(shù)，因?yàn)榧t黑樹(shù)是map和set的底層數(shù)據(jù)結(jié)構(gòu)這里我們實(shí)現(xiàn)出來(lái)紅黑樹(shù)就可以直接用當(dāng)前我們實(shí)現(xiàn)的帶頭紅黑樹(shù)來(lái)實(shí)現(xiàn)map和set至于頭節(jié)點(diǎn)的給出是為了方便于map和set的遍歷，在STL中我們區(qū)間給出都是左閉右開(kāi)區(qū)間的，既然紅黑樹(shù)作為map和set的底層數(shù)據(jù)結(jié)構(gòu)那么我們就一定有位置要來(lái)放map和set的迭代器，那么就可以將begin位置的迭代器放在head的左，end位置的迭代器可以放在head位置。這里我們將紅黑樹(shù)頭節(jié)點(diǎn)的顏色給為紅色。
3.2. 紅黑樹(shù)的節(jié)點(diǎn)
3.3. 紅黑樹(shù)插入節(jié)點(diǎn)的分析（實(shí)現(xiàn)紅黑樹(shù)最最最關(guān)鍵的一步）
可以看到我們上面在紅黑樹(shù)節(jié)點(diǎn)的構(gòu)造的時(shí)候?qū)⒐?jié)點(diǎn)的默認(rèn)顏色給為紅色，那么我們?cè)诓迦牍?jié)點(diǎn)的時(shí)候就要特別考慮性質(zhì)3：不可以有兩個(gè)紅色節(jié)點(diǎn)連在一起。這里我們可以一共可以分為兩大類，一類將節(jié)點(diǎn)插入當(dāng)前紅黑樹(shù)的左子樹(shù)中，另一類就是將節(jié)點(diǎn)插入紅黑樹(shù)的右子樹(shù)當(dāng)中。
第一大類（將節(jié)點(diǎn)插入紅黑樹(shù)的左子樹(shù)中）
第一種情況（叔叔節(jié)點(diǎn)存在而且為紅色，這里將節(jié)點(diǎn)插入紅黑樹(shù)的內(nèi)測(cè)還是內(nèi)測(cè)處理方式是一樣的）
1.我們插入節(jié)點(diǎn)的parent節(jié)點(diǎn)為黑色：那么這種情況是不需要調(diào)整的。
2.我們插入節(jié)點(diǎn)的parent節(jié)點(diǎn)為紅色，而且插入節(jié)點(diǎn)的叔叔節(jié)點(diǎn)也存在而且為紅色的，那么當(dāng)前節(jié)點(diǎn)插入之后就違反了紅黑樹(shù)的性質(zhì)3，就需要對(duì)當(dāng)前樹(shù)進(jìn)行調(diào)整。這里解決的時(shí)候我們就將當(dāng)前parent節(jié)點(diǎn)和叔叔節(jié)點(diǎn)u的顏色變?yōu)楹谏?/p>
為什么要這樣做呢？
答案：這里我們將cur節(jié)點(diǎn)插入之后要解決當(dāng)前parent和cur顏色都為紅色的問(wèn)題，那么只能將cur和parnet其中一個(gè)節(jié)點(diǎn)的顏色變?yōu)楹谏?，但是肯定不能將cur節(jié)點(diǎn)變?yōu)楹谏?，因?yàn)檫@樣在包含cur的路徑中就多一個(gè)黑色節(jié)點(diǎn)，那么我們就要將除包含cur之外的路徑中的黑色節(jié)點(diǎn)全部都減少一個(gè)，又因?yàn)榇藭r(shí)cur是新插入的節(jié)點(diǎn)如果將cur顏色變?yōu)楹谏敲创藭r(shí)就只有一條路徑黑色節(jié)點(diǎn)個(gè)數(shù)+1，如果要調(diào)整的話，其他所有節(jié)點(diǎn)中黑色節(jié)點(diǎn)個(gè)數(shù)都要減少一個(gè)這樣肯定是不行的，那么我們只能將parent節(jié)點(diǎn)的顏色變?yōu)楹谏?，那么?dāng)parent節(jié)點(diǎn)變?yōu)楹谏笪覀兛梢钥吹皆诎琾arent的路徑中黑色節(jié)點(diǎn)增加，但是包含parent節(jié)點(diǎn)的路徑一定包含parent的雙親節(jié)點(diǎn)也就是g節(jié)點(diǎn)那么我們將雙親節(jié)點(diǎn)g顏色改為紅色，那么不就將包含parent路徑的黑色節(jié)點(diǎn)個(gè)數(shù)減少一個(gè)了嗎。然后我們發(fā)現(xiàn)又出現(xiàn)新的問(wèn)題了，就是原本包含u節(jié)點(diǎn)的路徑因?yàn)間節(jié)點(diǎn)變?yōu)榱思t色那么包含u節(jié)點(diǎn)的路徑中少了一個(gè)黑色節(jié)點(diǎn)（因?yàn)榘瑄節(jié)點(diǎn)的路徑一定包含g節(jié)點(diǎn)）那么我們此時(shí)只要將u節(jié)點(diǎn)的顏色變?yōu)楹谏纯伞?/p>
上面將parent和u的節(jié)點(diǎn)更新為紅色之后，我們還要考慮g節(jié)點(diǎn)讓我們更新為紅色之后那它的雙親節(jié)點(diǎn)是否存在，是否是紅色節(jié)點(diǎn)：
相關(guān)視頻推薦
5種紅黑樹(shù)的場(chǎng)景，從Linux內(nèi)核談到Nginx源碼，聽(tīng)完醍醐灌頂
5種紅黑樹(shù)的用途，從應(yīng)用到內(nèi)核場(chǎng)景的優(yōu)缺點(diǎn)
如果g的雙親不存在：
那么此時(shí)g就是根節(jié)點(diǎn)那么我們此時(shí)需要將g顏色更新為黑色，因?yàn)榧t黑樹(shù)的根節(jié)點(diǎn)必須是黑色的。
如果g的雙親存在：
分為兩種情況：1、g的雙親為黑色那么調(diào)整結(jié)束直接退出。2、如果g的雙親為紅色（而且g的叔叔為紅色，這里如果g的叔叔為黑色我們下面會(huì)討論）那么我們更新cur和parent繼續(xù)當(dāng)前的調(diào)整過(guò)程。
我們可以總結(jié)一下我們的第一種情況：
第二種情況（叔叔節(jié)點(diǎn)存在而且一定為黑色或者叔叔節(jié)點(diǎn)不存在）
當(dāng)前cur節(jié)點(diǎn)是新插入節(jié)點(diǎn)，那么叔叔節(jié)點(diǎn)一定是不存在的
當(dāng)前cur不是新插入節(jié)點(diǎn)，那么就和我們第一種情況，我們更新完祖父節(jié)點(diǎn)后祖父節(jié)點(diǎn)還有叔叔節(jié)點(diǎn)的情況這時(shí)叔叔節(jié)點(diǎn)一定是黑色的，其實(shí)下面這種情況的出現(xiàn)就是為了解決上面第一種情況：更新完祖父節(jié)點(diǎn)之后祖父節(jié)點(diǎn)還有叔叔節(jié)點(diǎn)且叔叔節(jié)點(diǎn)為黑色。
那么我們?nèi)绾谓鉀Q當(dāng)前場(chǎng)景呢？
我們這里一共給出三步：
1.將parent節(jié)點(diǎn)改為黑色
2.將g節(jié)點(diǎn)改為紅色
3.將g節(jié)點(diǎn)右單旋
當(dāng)叔叔節(jié)點(diǎn)不存在也是一樣的做法
我們總結(jié)一下第二種情況：第二種情況其實(shí)就是對(duì)第一種情況其中的一種情況的分析解決。
第三種情況：第三種情況其實(shí)就是對(duì)第二種情況的變種，cur在parent的右側(cè)。
如果你可以堅(jiān)持看到這里，恭喜你你已經(jīng)理解了手撕紅黑樹(shù)中基本最難的地方了，馬上就能撕碎紅黑樹(shù)?。?！
情況三的解決方案：（其實(shí)情況三就是轉(zhuǎn)化為情況二來(lái)解決的）
至此我們就將紅黑樹(shù)插入的第一大類看完了，接下來(lái)就是第二大類基本就和我們的第一大類一樣，不同的地方就是第二大類將節(jié)點(diǎn)插入到紅黑樹(shù)的右子樹(shù)。
第二大類（將節(jié)點(diǎn)插入紅黑樹(shù)的右子樹(shù)中）
第一種情況：插入節(jié)點(diǎn)的parent節(jié)點(diǎn)為紅色而且叔叔節(jié)點(diǎn)存在為紅色（這里將節(jié)點(diǎn)插入紅黑樹(shù)的內(nèi)測(cè)還是內(nèi)測(cè)處理方式是一樣的）
那么我們和第一類中一樣也分為g有雙親節(jié)點(diǎn)（g的叔叔為紅色，g的叔叔為黑色兩種情況）和沒(méi)有雙親節(jié)點(diǎn)。
g沒(méi)有雙親節(jié)點(diǎn)：沒(méi)有雙親節(jié)點(diǎn)我們將g顏色更新為紅色直接返回即可。
g的雙親節(jié)點(diǎn)如果存在:那么我們就又分為兩種情況一種是雙親節(jié)點(diǎn)為黑色節(jié)點(diǎn)那么調(diào)整結(jié)束滿足紅黑樹(shù)性質(zhì)，另一種雙親節(jié)點(diǎn)為紅色那么，就又分為兩種情況：一種是當(dāng)前叔叔節(jié)點(diǎn)為紅色那么我們重復(fù)當(dāng)前的調(diào)整步驟，另一種就是我們下面情況二要討論的叔叔節(jié)點(diǎn)為黑色。
第二情況：叔叔節(jié)點(diǎn)存在但顏色一定是黑色||叔叔節(jié)點(diǎn)不存在
如果叔叔節(jié)點(diǎn)u為黑色節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)一定不是新插入節(jié)點(diǎn)。
那么就是我們遺留的第一種情況中未處理的情況就是下面這種情況：
由于與第一大類中第二種情況類似我們這里直接將解決方式給出，這里的叔叔節(jié)點(diǎn)不存在也是同樣的做法
第三種情況：叔叔節(jié)點(diǎn)存在但顏色一定是黑色||將節(jié)點(diǎn)插入內(nèi)側(cè)
4. 紅黑樹(shù)模擬實(shí)現(xiàn)
看到這里恭喜你，你已經(jīng)徹底掌握了紅黑樹(shù)的插入，接下來(lái)你可以動(dòng)手試一下紅黑樹(shù)的模擬實(shí)現(xiàn)，這里我也給出紅黑樹(shù)的模擬實(shí)現(xiàn)代碼可以作為參考。
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
// 節(jié)點(diǎn)的顏色
//我們可以使用 #define 定義常量，為什么非要使用枚舉？ 枚舉的優(yōu)點(diǎn)：
//1. 增加代碼的可讀性和可維護(hù)性
//2. 和#define定義的標(biāo)識(shí)符比較枚舉有類型檢查，更加嚴(yán)謹(jǐn)。
//3. 防止了命名污染（封裝）
//4. 便于調(diào)試
//5. 使用方便，一次可以定義多個(gè)常量
//6. 這些可能取值都是有值的，默認(rèn)從0開(kāi)始，一次遞增1，當(dāng)然在定義的時(shí)候也可以賦初值。
enum Color{ RED, BLACK };
// 紅黑樹(shù)節(jié)點(diǎn)的定義
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType(), Color color = RED)
//這里構(gòu)造節(jié)點(diǎn)的時(shí)候顏色默認(rèn)給為紅色因?yàn)槿绻o為黑色就有可能會(huì)破壞當(dāng)前紅黑樹(shù)的性質(zhì)，導(dǎo)致每條路徑的黑色節(jié)點(diǎn)個(gè)數(shù)不同
: _Left(nullptr), _Right(nullptr), _Parent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _Left; // 節(jié)點(diǎn)的左孩子
RBTreeNode<ValueType>* _Right; // 節(jié)點(diǎn)的右孩子
RBTreeNode<ValueType>* _Parent; // 節(jié)點(diǎn)的雙親(紅黑樹(shù)需要旋轉(zhuǎn)，為了實(shí)現(xiàn)簡(jiǎn)單給出該字段)
ValueType _data; // 節(jié)點(diǎn)的值域
Color _color; // 節(jié)點(diǎn)的顏色
};
//紅黑樹(shù)迭代器：
template<class T, class Ref, class Ptr>
struct RBTree_iterator
{
typedef RBTreeNode<T> Node;
typedef RBTree_iterator<T, Ref, Ptr> self;
//構(gòu)造函數(shù)就將紅黑樹(shù)的節(jié)點(diǎn)指針傳入進(jìn)來(lái)：
RBTree_iterator(Node* node = nullptr)
:_pnode(node)
{}
//迭代器解引用：
Ref operator*()
{
return _pnode->_data;
}
Ptr operator->()
{
return (&operator*());
}
//迭代器加加:前置加加
self operator++()
{
Increament();
return *this;
}
self operator++(int)
{
self temp = *this;
Increament();
return temp;
}
self operator--()
{
Decreament();
return *this;
}
self operator--(int)
{
self temp = *this;
Decreament();
return temp;
}
//將當(dāng)前迭代器指針的值放到后面大的值上
void Increament()
{
//如果當(dāng)前迭代器存在右子樹(shù)的時(shí)候我們將_pnode更新到右子樹(shù)
if (_pnode->_Right)
{
_pnode = _pnode->_Right;
//去右子樹(shù)中找最小的節(jié)點(diǎn)：
while (_pnode->_Left)
{
_pnode = _pnode->_Left;
}
}
else
{
Node* parent = _pnode->_Parent;
while (parent->_Right == _pnode)
{
_pnode = parent;
parent = _pnode->_Parent;
}
///----------------------------->>>>>>>>>>>一定要注意下面的情況當(dāng)紅黑樹(shù)沒(méi)有右子樹(shù)，那么當(dāng)前的head節(jié)點(diǎn)的右就指向
//紅黑樹(shù)的根那么此時(shí)如果將_pnode放在parent處那么就相當(dāng)于將while循環(huán)中的做了無(wú)用功。
if (_pnode->_Right != parent)
{
_pnode = parent;
}
}
}
void Decreament()
{
if (_pnode->_Parent->_Parent == _pnode&&_pnode->_color == RED)
{//當(dāng)前節(jié)點(diǎn)是head節(jié)點(diǎn)的時(shí)候那么我們就要找到當(dāng)最右邊節(jié)點(diǎn)也就是最大節(jié)點(diǎn)，而判斷當(dāng)前節(jié)點(diǎn)是否是最大的節(jié)點(diǎn)的時(shí)候
//不可只有一個(gè)_pnode->_Parent->_Parent因?yàn)楦?jié)點(diǎn)也滿足這個(gè)條件，因?yàn)槲覀儗⒓t黑樹(shù)的head節(jié)點(diǎn)設(shè)為紅色所以我們加上_color==RED
_pnode = _pnode->_Right;
}
//如果當(dāng)前的pnode的左子樹(shù)存在那么我們就將節(jié)點(diǎn)放在左子樹(shù)
else if (_pnode->_Left)
{
_pnode = _pnode->_Left;
while (_pnode->_Right)
{
_pnode = _pnode->_Right;
}
}
else
{
Node* parent = _pnode->_Parent;
//這里如果_pnode到了begin的位置就不可以再減了
while (_pnode == parent->_Left)
{
_pnode = parent;
parent = _pnode->_Parent;
}
_pnode = parent;
}
}
bool operator==(const self &s)const
{
return _pnode == s._pnode;
}
bool operator!=(const self &s)const
{
return _pnode != s._pnode;
}
Node* _pnode;
};
template<class T,class Keyofvalue>
class RBtree{
typedef RBTreeNode<T> Node;
public:
typedef RBTree_iterator<T, T&, T*> RBiterator;
public:
RBtree()
:_head(new Node()), _size(0)
{
_head->_Left = _head;
_head->_Right = _head;
}
pair<RBiterator,bool> insert(const T &val)//插入節(jié)點(diǎn)
{
Keyofvalue key;
//先按照二叉搜索樹(shù)的方式插入
Node* new_node=nullptr;
Node*& _root = get_root();
if (_root == nullptr)
{//為空樹(shù)
_root = new Node(val, RED);
_root->_Parent = _head;
new_node = _root;
//_head->_Parent = _root;
}
else
{//樹(shù)非空
Node* cur = _root;
Node* parent = _head;
while (cur)
{
parent = cur;
if (key(val) < key(cur->_data))
{
cur = cur->_Left;
}
else if (key(val)>key(cur->_data))
{
cur = cur->_Right;
}
else
{//我們這里不允許插入相同值域的節(jié)點(diǎn)
return make_pair(RBiterator(cur),false);
}
}
cur = new Node(val);
new_node = cur;
if (key(val) < key(parent->_data))
{
parent->_Left = cur;
}
else
{
parent->_Right = cur;
}
cur->_Parent = parent;
//插入成功之后我們調(diào)整當(dāng)前紅黑樹(shù)的節(jié)點(diǎn)：
//這里我們?cè)诓迦爰t黑樹(shù)中調(diào)整的時(shí)候只有當(dāng)?shù)谝恢星闆r才繼續(xù)向上更新節(jié)點(diǎn)，那么我們只要考慮第一中情況的終止條件即可
//第一中情況中如果parent為紅色節(jié)點(diǎn)那么當(dāng)前節(jié)點(diǎn)就需要繼續(xù)向上更新，但是我們將head節(jié)點(diǎn)也設(shè)為紅色那么當(dāng)我們parent
//節(jié)點(diǎn)更新到head節(jié)點(diǎn)那么當(dāng)前也就不更新了
while (parent != _head&&parent->_color == RED)
{
//插入節(jié)點(diǎn)雙親為黑色：
if (parent->_color == BLACK)
{
break;
}
else
{//插入節(jié)點(diǎn)雙親為紅色
Node* grandparent = parent->_Parent;//這里如果雙親的節(jié)點(diǎn)是紅色那么雙親一定是有雙親節(jié)點(diǎn)的
if (parent == grandparent->_Left)
{//第一大類插入節(jié)點(diǎn)在紅黑樹(shù)的左子樹(shù)：
Node* uncle = grandparent->_Right;//當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)
if (uncle&&uncle->_color == RED)
{//第一種情況：叔叔節(jié)點(diǎn)存在而且為紅色：
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
cur = grandparent;
parent = cur->_Parent;
}
//第二三種情況：
else
{
//因?yàn)槲覀円獙⒌谌N情況轉(zhuǎn)化為第二種情況處理所以我們先寫第三種情況：cur插在內(nèi)側(cè)
if (cur == parent->_Right)
{
rotate_left(parent);
std::swap(parent, cur);
}
//第二種情況：先將parent和grandparent顏色互換然后右旋
parent->_color = BLACK;
grandparent->_color = RED;
rotate_right(grandparent);
}
}
else
{//第二大類插入節(jié)點(diǎn)在紅黑樹(shù)的右子樹(shù)：
Node* uncle = grandparent->_Left;//當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)
if (uncle&&uncle->_color == RED)
{//第一種情況：叔叔節(jié)點(diǎn)存在而且為紅色：
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
cur = grandparent;
parent = cur->_Parent;
}
//第二三種情況：
else
{
//因?yàn)槲覀円獙⒌谌N情況轉(zhuǎn)化為第二種情況處理所以我們先寫第三種情況：cur插在內(nèi)側(cè)
if (cur == parent->_Left)
{
rotate_right(parent);
std::swap(parent, cur);
}
//第二種情況：先將parent和grandparent顏色互換然后右旋
parent->_color = BLACK;
grandparent->_color = RED;
rotate_left(grandparent);
}
}
}
}
}
_root->_color = BLACK;
_head->_Left = get_mostleftnode();
_head->_Right = get_mostrightnode();
return make_pair(RBiterator(new_node), true);
}
//這里的銷毀節(jié)點(diǎn)一定要傳&因?yàn)橐驗(yàn)橄旅嬉薷膔oot=nullptr的時(shí)候要將指針?biāo)赶虻牡刂沸薷臑閚ullptr不然如果后面再調(diào)用destroy的時(shí)候
//其實(shí)root所指向的地址并沒(méi)有指向nullptr所以就有可能出錯(cuò)。
void Destroy(Node* &root)
{
if (root)
{
Destroy(root->_Left);
Destroy(root->_Right);
delete root;
root = nullptr;
}
}
void Clear()
{
Destroy(get_root());
_size = 0;
}
~RBtree()
{
Destroy(get_root());
delete _head;
}
//查找方法
RBiterator Find(T value)
{
Keyofvalue key;
Node* cur = get_root();
while (cur)
{
if (key(cur->_data) < key(value))
{
cur = cur->_Right;
}
else if (key(cur->_data)>key(value))
{
cur = cur->_Left;
}
else
{
return RBiterator(cur);
}
}
return End();
}
RBiterator End()
{
return RBiterator(_head);
}
RBiterator Begin()
{
return RBiterator(_head->_Left);
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return _size == 0;
}
//中序遍歷//
void inoder()
{
cout << "中序遍歷結(jié)果為：";
Node* _root = get_root();
mid(_root);
cout << endl;
}
/判斷當(dāng)前樹(shù)是否是紅黑樹(shù)//
bool isRBtree()
{
Node* root = get_root();
if (root == nullptr)
{
return true;
}
//判斷根節(jié)點(diǎn)是否是黑色節(jié)點(diǎn)：
if (root->_color == RED)
{
return false;
}
//判斷每條路徑中黑色節(jié)點(diǎn)個(gè)數(shù)是否相同
size_t black_count = 0;
Node* cur = root;
while (cur)
{
if (cur->_color == BLACK)
{
black_count++;
}
cur = cur->_Left;
}
int k = 0;
return _isRBtree(black_count, k, root);
}
//判斷紅黑樹(shù)中是否滿足性質(zhì)三（兩個(gè)紅色節(jié)點(diǎn)不挨在一起）性質(zhì)四（每條路徑中黑色節(jié)點(diǎn)樹(shù)相同）
bool _isRBtree(size_t black_count, int k, Node* root)
{
if (root == nullptr)
{
if (k != black_count)
{
cout << "當(dāng)前樹(shù)不是紅黑樹(shù)，有一條路徑黑色節(jié)點(diǎn)個(gè)數(shù)為：" << k << "少于路徑節(jié)點(diǎn)：" << black_count << endl;
return false;
}
return true;
}
if (root->_color == BLACK)
{
k++;
}
else
{
if (root->_Parent->_color == RED)
{
cout << "當(dāng)前樹(shù)不是紅黑樹(shù),有兩個(gè)紅色節(jié)點(diǎn)挨在一起。" << endl;
return false;
}
}
return _isRBtree(black_count, k, root->_Left) && _isRBtree(black_count, k, root->_Right);
}
/
void Swap(RBtree<T,Keyofvalue> _t)
{
std::swap(_head, _t._head);
}
private:
//中序遍歷：
void mid(Node* root)
{
if (root)
{
mid(root->_Left);
cout << root->_data << " ";
mid(root->_Right);
}
}
//這里因?yàn)槲覀兗t黑樹(shù)中沒(méi)有設(shè)置根節(jié)點(diǎn)在代碼實(shí)現(xiàn)的時(shí)候不容易理解所以這里我們寫一個(gè)私有函數(shù)返回紅黑樹(shù)的根節(jié)點(diǎn)：
Node* &get_root()
{
return _head->_Parent;
}
//獲取最左側(cè)節(jié)點(diǎn)也就是最小節(jié)點(diǎn)：
Node* get_mostleftnode()
{
Node* _root = get_root();
if (_root)
{
while (_root->_Left)
{
_root = _root->_Left;
}
}
return _root;
}
//獲取最右側(cè)節(jié)點(diǎn)也就是最大節(jié)點(diǎn)：
Node* get_mostrightnode()
{
Node* _root = get_root();
if (_root)
{
while (_root->_Right)
{
_root = _root->_Right;
}
}
return _root;
}
//左單旋
void rotate_left(Node* parent)
{
Node* pparent = parent->_Parent;
Node* subR = parent->_Right;
Node* subRL = subR->_Left;
parent->_Right = subRL;
//更新subRL的雙親：
if (subRL)
{
subRL->_Parent = parent;
}
subR->_Left = parent;
parent->_Parent = subR;
subR->_Parent = pparent;
if (pparent == _head)//------------------------------------->>>>一定要注意這里的pparent如果是頭節(jié)點(diǎn)那么一定要將pparent的指向?yàn)閟ubR
{
_head->_Parent = subR;
}
if (pparent)
{
if (pparent->_Left == parent)
{
pparent->_Left = subR;
}
else
{
pparent->_Right = subR;
}
}
}
//右單旋
void rotate_right(Node* parent)
{
Node* subL = parent->_Left;
Node* subLR = subL->_Right;
Node* pparent = parent->_Parent;
parent->_Left = subLR;
//如果subLR存在那么將其父節(jié)點(diǎn)更新
if (subLR)
{
subLR->_Parent = parent;
}
//將parent右旋下來(lái)：
subL->_Right = parent;
//parent旋下來(lái)就要更新parent的父節(jié)點(diǎn)
parent->_Parent = subL;
//此時(shí)subL就要更新父節(jié)點(diǎn)
subL->_Parent = pparent;
if (pparent == _head)
{
_head->_Parent = subL;
}
if (pparent)
{
if (parent == pparent->_Right)
{
pparent->_Right = subL;
}
else
{
pparent->_Left = subL;
}
}
}
private:
size_t _size;
Node* _head;
};
5. 基于紅黑樹(shù)的map的模擬實(shí)現(xiàn)
#pragma once
#include"RBtree.hpp"
//紅黑樹(shù)里面放的鍵值對(duì)
namespace wbx
{
template<class K,class V>
class map
{
public:
typedef pair<K,V> valuetype;
//這里是因?yàn)槲覀兗t黑樹(shù)中存放的是鍵值對(duì)，而我們紅黑樹(shù)在實(shí)現(xiàn)的時(shí)候只有一個(gè)模板類型參數(shù)，
//也就是我們要存放在紅黑樹(shù)中的節(jié)點(diǎn)，而我們的map是用pair（鍵值對(duì)來(lái)存放節(jié)點(diǎn)的）但是比較
//的時(shí)候我們是通過(guò)pair中的key值來(lái)比較的，所以我們這里就要定義一個(gè)類來(lái)返回我們map中要
//比較的類型。
struct Keyofvalue
{
const K&operator()(const valuetype &value)
{
return value.first;
}
};
typedef RBtree<valuetype,Keyofvalue> Tree;
typedef typename Tree::RBiterator iterator;
map()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
size_t empty()const
{
return _t.Empty();
}
//這里map的operator[]我們實(shí)現(xiàn)的時(shí)候直接用insert來(lái)實(shí)現(xiàn)，這里我們?cè)诩t黑樹(shù)中實(shí)現(xiàn)insert的時(shí)候
//是不允許插入相同的元素的，所以這里我們operator[]如果是一個(gè)新的key值那么我們就將其直接
//插入了如果是一個(gè)原有的key值那么紅黑樹(shù)中的inset插入就會(huì)將它的迭代器返回那么我們這里將
//返回的迭代器解引用得到它的value值的引用那么我就可以對(duì)其進(jìn)行修改
V& operator[](const K& key)
{
return (*(_t.insert(make_pair(key, V() ) ).first ) ).second;
}
pair<iterator, bool> insert(const valuetype& val)
{
return _t.insert(val);
}
void swap(map<K, V>& m)
{
_t.Swap(m._t);
}
void clear()
{
_t.Clear();
}
iterator find(const K& key )
{
return _t.Find(make_pair(key,V()));
}
private:
Tree _t;
};
};
6. 基于紅黑樹(shù)的set的模擬實(shí)現(xiàn)
#pragma once
#include"RBtree.hpp"
//紅黑樹(shù)里面放的鍵值對(duì)
namespace wbx
{
template<class K>
class set
{
public:
typedef K valuetype;
struct Keyofvalue
{
const K&operator()(const valuetype &value)
{
return value;
}
};
typedef RBtree<valuetype, Keyofvalue> Tree;
typedef typename Tree::RBiterator iterator;
set()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
size_t empty()const
{
return _t.Empty();
}
pair<iterator, bool> insert(const valuetype& val)
{
return _t.insert(val);
}
void swap(set<K>& s)
{
_t.Swap(s._t);
}
void clear()
{
_t.Clear();
}
iterator find(const valuetype& key)
{
return _t.Find(key);
}
private:
Tree _t;
};
};
end
更多信息可以來(lái)這里獲取==>>電子技術(shù)應(yīng)用-AET<<
電子技術(shù)應(yīng)用專欄作家 一口linux
原文鏈接：https://mp.weixin.qq.com/s/MGUMK8SQLD7unuIaRegsZQ