什么是紅黑樹(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)楹谏强隙ú荒軐ur節(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