?

?📝個人主頁：@Sherry的成長之路
🏠學(xué)習(xí)社區(qū)：Sherry的成長之路（個人社區(qū)）
📖專欄鏈接：數(shù)據(jù)結(jié)構(gòu)
🎯長路漫漫浩浩，萬事皆有期待

上一篇博客：【數(shù)據(jù)結(jié)構(gòu)】AVL樹(C++實現(xiàn))

紅黑樹的概念

紅黑樹是一種二叉搜索樹，但在每個結(jié)點上增加了一個存儲位用于表示結(jié)點的顏色，這個顏色可以是紅色的，也可以是黑色的，因此我們稱之為紅黑樹。

紅黑樹通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，確保沒有一條路徑會比其他路徑長出兩倍，因此紅黑樹是近似平衡的。

紅黑樹的性質(zhì)

紅黑樹有以下五點性質(zhì)：

每個結(jié)點不是紅色就是黑色。
根結(jié)點是黑色的。
如果一個結(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的。
對于每個結(jié)點，從該結(jié)點到其所有后代葉子結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點。
每個葉子結(jié)點都是黑色的（此處的葉子結(jié)點指定是空結(jié)點）。

紅黑樹如何確保從根到葉子的最長可能路徑不會超過最短可能路徑的兩倍？

根據(jù)紅黑樹的性質(zhì)3可以得出，紅黑樹當(dāng)中不會出現(xiàn)連續(xù)的紅色結(jié)點，而根據(jù)性質(zhì)4又可以得出，從某一結(jié)點到其后代葉子結(jié)點的所有路徑上包含的黑色結(jié)點的數(shù)目是相同的。

我們假設(shè)在紅黑樹中，從根到葉子的所有路徑上包含的黑色結(jié)點的個數(shù)都是N個，那么最短路徑就是全部由黑色結(jié)點構(gòu)成的路徑，即長度為N。

而最長可能路徑就是由一黑一紅結(jié)點構(gòu)成的路徑，該路徑當(dāng)中黑色結(jié)點與紅色結(jié)點的數(shù)目相同，即長度為2N。

因此，紅黑樹從根到葉子的最長可能路徑不會超過最短可能路徑的兩倍。

紅黑樹結(jié)點的定義

我們這里直接實現(xiàn)KV模型的紅黑樹，為了方便后序的旋轉(zhuǎn)操作，將紅黑樹的結(jié)點定義為三叉鏈結(jié)構(gòu)，除此之外還新加入了一個成員變量，用于表示結(jié)點的顏色。

template<class K, class V>
struct RBTreeNode
{//三叉鏈RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//存儲的鍵值對pair<K, V> _kv;//結(jié)點的顏色int _col; //紅/黑//構(gòu)造函數(shù)RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

在這里我們可以使用枚舉來定義結(jié)點的顏色，這樣可以增加代碼的可讀性和可維護(hù)性，并且便于后序的調(diào)試操作。

//枚舉定義結(jié)點的顏色
enum Colour
{RED,BLACK
};

為什么構(gòu)造結(jié)點時，默認(rèn)將結(jié)點的顏色設(shè)置為紅色？

當(dāng)我們向紅黑樹插入結(jié)點時，若我們插入的是黑色結(jié)點，那么插入路徑上黑色結(jié)點的數(shù)目就比其他路徑上黑色結(jié)點的數(shù)目多了一個，即破壞了紅黑樹的性質(zhì)4，此時我們就需要對紅黑樹進(jìn)行調(diào)整。

若我們插入紅黑樹的結(jié)點是紅色的，此時如果其父結(jié)點也是紅色的，那么表明出現(xiàn)了連續(xù)的紅色結(jié)點，即破壞了紅黑樹的性質(zhì)3，此時我們需要對紅黑樹進(jìn)行調(diào)整；但如果其父結(jié)點是黑色的，那我們就無需對紅黑樹進(jìn)行調(diào)整，插入后仍滿足紅黑樹的要求。

總結(jié)一下：

插入黑色結(jié)點，一定破壞紅黑樹的性質(zhì)4，必須對紅黑樹進(jìn)行調(diào)整。
插入紅色結(jié)點，可能破壞紅黑樹的性質(zhì)3，可能對紅黑樹進(jìn)行調(diào)整。

權(quán)衡利弊后，我們在構(gòu)造結(jié)點進(jìn)行插入時，默認(rèn)將結(jié)點的顏色設(shè)置為紅色。

紅黑樹的插入

紅黑樹插入結(jié)點的邏輯分為三步：

按二叉搜索樹的插入方法，找到待插入位置。
將待插入結(jié)點插入到樹中。
若插入結(jié)點的父結(jié)點是紅色的，則需要對紅黑樹進(jìn)行調(diào)整。

其中前兩步與二叉搜索樹插入結(jié)點時的邏輯相同，紅黑樹的關(guān)鍵在于第三步對紅黑樹的調(diào)整。

紅黑樹在插入結(jié)點后是如何調(diào)整的？

實際上，在插入結(jié)點后并不是一定會對紅黑樹進(jìn)行調(diào)整，若插入結(jié)點的父結(jié)點是黑色的，那么我們就不用對紅黑樹進(jìn)行調(diào)整，因為本次結(jié)點的插入并沒有破壞紅黑樹的五點性質(zhì)。

只有當(dāng)插入結(jié)點的父結(jié)點是紅色時才需要對紅黑樹進(jìn)行調(diào)整，因為我們默認(rèn)插入的結(jié)點就是紅色的，如果插入結(jié)點的父結(jié)點也是紅色的，那么此時就出現(xiàn)了連續(xù)的紅色結(jié)點，因此需要對紅黑樹進(jìn)行調(diào)整。

因為插入結(jié)點的父結(jié)點是紅色的，說明父結(jié)點不是根結(jié)點（根結(jié)點是黑色的），因此插入結(jié)點的祖父結(jié)點（父結(jié)點的父結(jié)點）就一定存在。

紅黑樹調(diào)整時具體應(yīng)該如何調(diào)整，主要是看插入結(jié)點的叔叔（插入結(jié)點的父結(jié)點的兄弟結(jié)點），根據(jù)插入結(jié)點叔叔的不同，可將紅黑樹的調(diào)整分為三種情況。

情況一：插入結(jié)點的叔叔存在，且叔叔的顏色是紅色。

此時為了避免出現(xiàn)連續(xù)的紅色結(jié)點，我們可以將父結(jié)點變黑，但為了保持每條路徑黑色結(jié)點的數(shù)目不變，因此我們還需要將祖父結(jié)點變紅，再將叔叔變黑。這樣一來既保持了每條路徑黑色結(jié)點的數(shù)目不變，也解決了連續(xù)紅色結(jié)點的問題。

但調(diào)整還沒有結(jié)束，因為此時祖父結(jié)點變成了紅色，如果祖父結(jié)點是根結(jié)點，那我們直接再將祖父結(jié)點變成黑色即可，此時相當(dāng)于每條路徑黑色結(jié)點的數(shù)目都增加了一個。

但如果祖父結(jié)點不是根結(jié)點的話，我們就需要將祖父結(jié)點當(dāng)作新插入的結(jié)點，再判斷其父結(jié)點是否為紅色，若其父結(jié)點也是紅色，那么又需要根據(jù)其叔叔的不同，進(jìn)而進(jìn)行不同的調(diào)整操作。

因此，情況一的抽象圖表示如下：

注意： 叔叔存在且為紅時，cur結(jié)點是parent的左孩子還是右孩子，調(diào)整方法都是一樣的。

情況二：插入結(jié)點的叔叔存在，且叔叔的顏色是黑色。

這種情況一定是在情況一繼續(xù)往上調(diào)整的過程中出現(xiàn)的，即這種情況下的cur結(jié)點一定不是新插入的結(jié)點，而是上一次情況一調(diào)整過程中的祖父結(jié)點，如下圖：

我們將路徑中祖父結(jié)點之上黑色結(jié)點的數(shù)目設(shè)為x xx，將叔叔結(jié)點之下黑色結(jié)點的數(shù)目設(shè)為y yy，則在插入結(jié)點前，圖示兩條路徑黑色結(jié)點的數(shù)目分別為x+1 和x+2+y，很明顯x+2+y 是一定大于 x+1的，因此在插入結(jié)點前就不滿足紅黑樹的要求了，所以說叔叔結(jié)點存在且為黑這種情況，一定是由情況一往上調(diào)整過程中才會出現(xiàn)的一種情況。

需要注意：

從根結(jié)點一直走到空位置就算一條路徑，而不是從根結(jié)點走到左右結(jié)點均為空的葉子結(jié)點時才算一條路徑。
情況二和情況三均需要進(jìn)行旋轉(zhuǎn)處理，旋轉(zhuǎn)處理后無需繼續(xù)往上進(jìn)行調(diào)整，所以說情況二一定是由情況一往上調(diào)整的過程中出現(xiàn)的。

出現(xiàn)叔叔存在且為黑時，單純使用變色已經(jīng)無法處理了，這時我們需要進(jìn)行旋轉(zhuǎn)處理。若祖孫三代的關(guān)系是直線（cur、parent、grandfather這三個結(jié)點為一條直線），則我們需要先進(jìn)行單旋操作，再進(jìn)行顏色調(diào)整，顏色調(diào)整后這棵被旋轉(zhuǎn)子樹的根結(jié)點是黑色的，因此無需繼續(xù)往上進(jìn)行處理。

抽象圖表示如下：

說明一下： 當(dāng)直線關(guān)系為，parent是grandfather的右孩子，cur是parent的右孩子時，就需要先進(jìn)行左單旋操作，再進(jìn)行顏色調(diào)整。

若祖孫三代的關(guān)系是折現(xiàn)（cur、parent、grandfather這三個結(jié)點為一條折現(xiàn)），則我們需要先進(jìn)行雙旋操作，再進(jìn)行顏色調(diào)整，顏色調(diào)整后這棵被旋轉(zhuǎn)子樹的根是黑色的，因此無需繼續(xù)往上進(jìn)行處理。

抽象圖表示如下：

說明一下： 當(dāng)折現(xiàn)關(guān)系為，parent是grandfather的右孩子，cur是parent的左孩子時，就需要先進(jìn)行右左雙旋操作，再進(jìn)行顏色調(diào)整。

情況三：插入結(jié)點的叔叔不存在。

在這種情況下的cur結(jié)點一定是新插入的結(jié)點，而不可能是由情況一變化而來的，因為叔叔不存在說明在parent的下面不可能再掛黑色結(jié)點了，如下圖：

如果插入前parent下面再掛黑色結(jié)點，就會導(dǎo)致圖中兩條路徑黑色結(jié)點的數(shù)目不相同，而parent是紅色的，因此parent下面自然也不能掛紅色結(jié)點，所以說這種情況下的cur結(jié)點一定是新插入的結(jié)點。

和情況二一樣，若祖孫三代的關(guān)系是直線（cur、parent、grandfather這三個結(jié)點為一條直線），則我們需要先進(jìn)行單旋操作，再進(jìn)行顏色調(diào)整，顏色調(diào)整后這棵被旋轉(zhuǎn)子樹的根結(jié)點是黑色的，因此無需繼續(xù)往上進(jìn)行處理。

抽象圖表示如下：

說明一下： 當(dāng)直線關(guān)系為，parent是grandfather的右孩子，cur是parent的右孩子時，就需要先進(jìn)行左單旋操作，再進(jìn)行顏色調(diào)整。

若祖孫三代的關(guān)系是折現(xiàn)（cur、parent、grandfather這三個結(jié)點為一條折現(xiàn)），則我們需要先進(jìn)行雙旋操作，再進(jìn)行顏色調(diào)整，顏色調(diào)整后這棵被旋轉(zhuǎn)子樹的根是黑色的，因此無需繼續(xù)往上進(jìn)行處理。

抽象圖表示如下：

說明一下： 當(dāng)折現(xiàn)關(guān)系為，parent是grandfather的右孩子，cur是parent的左孩子時，就需要先進(jìn)行右左雙旋操作，再進(jìn)行顏色調(diào)整。

代碼如下：

//插入函數(shù)
pair<Node*, bool> Insert(const pair<K, V>& kv)
{if (_root == nullptr) //若紅黑樹為空樹，則插入結(jié)點直接作為根結(jié)點{_root = new Node(kv);_root->_col = BLACK; //根結(jié)點必須是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索樹的插入方法，找到待插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first) //待插入結(jié)點的key值小于當(dāng)前結(jié)點的key值{//往該結(jié)點的左子樹走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //待插入結(jié)點的key值大于當(dāng)前結(jié)點的key值{//往該結(jié)點的右子樹走parent = cur;cur = cur->_right;}else //待插入結(jié)點的key值等于當(dāng)前結(jié)點的key值{return make_pair(cur, false); //插入失敗}}//2、將待插入結(jié)點插入到樹中cur = new Node(kv); //根據(jù)所給值構(gòu)造一個結(jié)點Node* newnode = cur; //記錄新插入的結(jié)點（便于后序返回）if (kv.first < parent->_kv.first) //新結(jié)點的key值小于parent的key值{//插入到parent的左邊parent->_left = cur;cur->_parent = parent;}else //新結(jié)點的key值大于parent的key值{//插入到parent的右邊parent->_right = cur;cur->_parent = parent;}//3、若插入結(jié)點的父結(jié)點是紅色的，則需要對紅黑樹進(jìn)行調(diào)整while (parent&&parent->_col == RED){Node* grandfather = parent->_parent; //parent是紅色，則其父結(jié)點一定存在if (parent == grandfather->_left) //parent是grandfather的左孩子{Node* uncle = grandfather->_right; //uncle是grandfather的右孩子if (uncle&&uncle->_col == RED) //情況1：uncle存在且為紅{//顏色調(diào)整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續(xù)往上處理cur = grandfather;parent = cur->_parent;}else //情況2+情況3：uncle不存在 + uncle存在且為黑{if (cur == parent->_left){RotateR(grandfather); //右單旋//顏色調(diào)整grandfather->_col = RED;parent->_col = BLACK;}else //cur == parent->_right{RotateLR(grandfather); //左右雙旋//顏色調(diào)整grandfather->_col = RED;cur->_col = BLACK;}break; //子樹旋轉(zhuǎn)后，該子樹的根變成了黑色，無需繼續(xù)往上進(jìn)行處理}}else //parent是grandfather的右孩子{Node* uncle = grandfather->_left; //uncle是grandfather的左孩子if (uncle&&uncle->_col == RED) //情況1：uncle存在且為紅{//顏色調(diào)整uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//繼續(xù)往上處理cur = grandfather;parent = cur->_parent;}else //情況2+情況3：uncle不存在 + uncle存在且為黑{if (cur == parent->_left){RotateRL(grandfather); //右左雙旋//顏色調(diào)整cur->_col = BLACK;grandfather->_col = RED;}else //cur == parent->_right{RotateL(grandfather); //左單旋//顏色調(diào)整grandfather->_col = RED;parent->_col = BLACK;}break; //子樹旋轉(zhuǎn)后，該子樹的根變成了黑色，無需繼續(xù)往上進(jìn)行處理}}}_root->_col = BLACK; //根結(jié)點的顏色為黑色（可能被情況一變成了紅色，需要變回黑色）return make_pair(newnode, true); //插入成功
}//左單旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;//建立subRL與parent之間的聯(lián)系parent->_right = subRL;if (subRL)subRL->_parent = parent;//建立parent與subR之間的聯(lián)系subR->_left = parent;parent->_parent = subR;//建立subR與parentParent之間的聯(lián)系if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}//右單旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;//建立subLR與parent之間的聯(lián)系parent->_left = subLR;if (subLR)subLR->_parent = parent;//建立parent與subL之間的聯(lián)系subL->_right = parent;parent->_parent = subL;//建立subL與parentParent之間的聯(lián)系if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}
}//左右雙旋
void RotateLR(Node* parent)
{RotateL(parent->_left);RotateR(parent);
}//右左雙旋
void RotateRL(Node* parent)
{RotateR(parent->_right);RotateL(parent);
}

注意： 在紅黑樹調(diào)整后，需要將根結(jié)點的顏色變?yōu)楹谏?#xff0c;因為紅黑樹的根結(jié)點可能在情況一的調(diào)整過程中被變成了紅色。

紅黑樹的驗證

紅黑樹也是一種特殊的二叉搜索樹，因此我們可以先獲取二叉樹的中序遍歷序列，來判斷該二叉樹是否滿足二叉搜索樹的性質(zhì)。

代碼如下：

//中序遍歷
void Inorder()
{_Inorder(_root);
}
//中序遍歷子函數(shù)
void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);
}

但中序有序只能證明是二叉搜索樹，要證明二叉樹是紅黑樹還需驗證該二叉樹是否滿足紅黑樹的性質(zhì)。

代碼如下：

//判斷是否為紅黑樹
bool ISRBTree()
{if (_root == nullptr) //空樹是紅黑樹{return true;}if (_root->_col == RED){cout << "error：根結(jié)點為紅色" << endl;return false;}//找最左路徑作為黑色結(jié)點數(shù)目的參考值Node* cur = _root;int BlackCount = 0;while (cur){if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}int count = 0;return _ISRBTree(_root, count, BlackCount);
}
//判斷是否為紅黑樹的子函數(shù)
bool _ISRBTree(Node* root, int count, int BlackCount)
{if (root == nullptr) //該路徑已經(jīng)走完了{if (count != BlackCount){cout << "error：黑色結(jié)點的數(shù)目不相等" << endl;return false;}return true;}if (root->_col == RED&&root->_parent->_col == RED){cout << "error：存在連續(xù)的紅色結(jié)點" << endl;return false;}if (root->_col == BLACK){count++;}return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);
}

紅黑樹的查找

紅黑樹的查找函數(shù)與二叉搜索樹的查找方式一模一樣，邏輯如下：

若樹為空樹，則查找失敗，返回nullptr。
若key值小于當(dāng)前結(jié)點的值，則應(yīng)該在該結(jié)點的左子樹當(dāng)中進(jìn)行查找。
若key值大于當(dāng)前結(jié)點的值，則應(yīng)該在該結(jié)點的右子樹當(dāng)中進(jìn)行查找。
若key值等于當(dāng)前結(jié)點的值，則查找成功，返回對應(yīng)結(jié)點。

代碼如下：

//查找函數(shù)
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (key < cur->_kv.first) //key值小于該結(jié)點的值{cur = cur->_left; //在該結(jié)點的左子樹當(dāng)中查找}else if (key > cur->_kv.first) //key值大于該結(jié)點的值{cur = cur->_right; //在該結(jié)點的右子樹當(dāng)中查找}else //找到了目標(biāo)結(jié)點{return cur; //返回該結(jié)點}}return nullptr; //查找失敗
}

紅黑樹的刪除

紅黑樹的刪除要比插入更加難以理解，但是只要仔細(xì)一點也還行。

第一步：找到實際待刪除的結(jié)點

找結(jié)點的過程與二叉搜索樹尋找待刪除結(jié)點的方法一樣，若找到的待刪除結(jié)點的左右子樹均不為空，則需要使用替換法進(jìn)行刪除。因此我們最終需要刪除的都是左右子樹至少有一個為空的結(jié)點。

找到實際待刪除結(jié)點后，先不刪除該結(jié)點，否則調(diào)整紅黑樹時不容易控制，找到實際待刪除結(jié)點后立即進(jìn)行紅黑樹的調(diào)整。

第二步：調(diào)整紅黑樹

調(diào)整紅黑樹之前，我們先判斷一下本次結(jié)點的刪除是否會破壞了紅黑樹的性質(zhì)，若破壞了我們才需要對紅黑樹進(jìn)行調(diào)整。

若實際刪除的結(jié)點是紅色結(jié)點，那么本次刪除操作不會破壞紅黑樹的性質(zhì)，因此我們不需要對紅黑樹進(jìn)行調(diào)整。反之，若刪除的結(jié)點是黑色結(jié)點，我們就需要對紅黑樹進(jìn)行調(diào)整，因為黑色結(jié)點的刪除將會使得一些路徑中黑色結(jié)點的數(shù)目減少，此時便破壞了紅黑樹的性質(zhì)四。

我們先來說最簡單的一種情況，即待刪除結(jié)點只有一個孩子為空的情況。

在這種情況下，待刪除結(jié)點要么是只有左孩子，要么是有只右孩子，但不管是左孩子還是右孩子，這個孩子一定是紅色的，因為若這個孩子是黑色的，那么此時圖示長藍(lán)色路徑的黑色結(jié)點數(shù)目比短藍(lán)色路徑的黑色結(jié)點數(shù)目多，不符合紅黑樹的性質(zhì)。

又因為紅黑樹當(dāng)中不允許出現(xiàn)連續(xù)的紅色結(jié)點，因此在這種情況下實際上就只有圖示兩種實際情況，這時我們直接將待刪除結(jié)點的那個紅孩子變成黑色就行了，因為在后面實際刪除結(jié)點時會將這個孩子連接到刪除結(jié)點的父結(jié)點下面，連接后相當(dāng)于我們刪除的是一個紅色結(jié)點，紅黑樹調(diào)整完成。

下面再來說比較復(fù)雜的情況，即待刪除結(jié)點的左右孩子均為空。

我們以待刪除結(jié)點是其父結(jié)點的左孩子為例，分為以下四種情況：

圖示說明：

若parent結(jié)點為白色，表明parent結(jié)點可能是紅色結(jié)點也可能是黑色結(jié)點。
若bL或bR結(jié)點為白色，表明其可能是紅色結(jié)點或黑色結(jié)點甚至該結(jié)點不存在。
bL和bR結(jié)點為黑色時，表明他們可能是黑色結(jié)點或該結(jié)點不存在。

情況一：brother為紅色。

當(dāng)待刪除結(jié)點的brother為紅色時，我們先以parent為旋轉(zhuǎn)點進(jìn)行一次左單旋，再將brother的顏色變?yōu)楹谏?#xff0c;將parent的顏色變?yōu)榧t色，此時我們再對待刪除結(jié)點cur進(jìn)行情況分析，情況一就轉(zhuǎn)換成了情況二、三或四。

情況二：brother為黑色，且其左右孩子都是黑色結(jié)點或為空。

在該情況下，我們直接將brother的顏色變成紅色，此時根據(jù)parent的顏色決定紅黑樹的調(diào)整是否結(jié)束，若parent的顏色是紅色，則我們將parent變?yōu)楹谏蠹纯山Y(jié)束紅黑樹的調(diào)整；若parent的顏色原本就是黑色，則我們需要將parent結(jié)點當(dāng)作下一次調(diào)整時的cur結(jié)點進(jìn)行情況分析，并且情況二在下一次調(diào)整時可能會是情況一、二、三、四當(dāng)中的任何一種。

情況三：brother為黑色，且其左孩子是紅色結(jié)點，右孩子是黑色結(jié)點或為空。

出現(xiàn)該情況時，我們先以brother為旋轉(zhuǎn)點進(jìn)行一次右單旋，再將brother結(jié)點變?yōu)榧t色，將brotherLeft變?yōu)楹谏?#xff0c;此時我們再對待刪除結(jié)點cur進(jìn)行情況分析，情況三就轉(zhuǎn)換成了情況四。

情況四：brother為黑色，且其右孩子是紅色結(jié)點。

經(jīng)過情況四的處理后，紅黑樹就一定調(diào)整結(jié)束了。在情況四當(dāng)中，我們先以parent為旋轉(zhuǎn)點進(jìn)行一次左單旋，然后將parent的顏色賦值給brother，再將parent的顏色變?yōu)楹谏?#xff0c;最后將brotherRight變?yōu)楹谏?#xff0c;此時紅黑樹的調(diào)整便結(jié)束了。

說明一下：

待刪除結(jié)點是其父結(jié)點的右孩子時的四種情況與上面四種情況類似，這里就不列舉出來了。
若待刪除結(jié)點沒有父結(jié)點，即待刪除結(jié)點是根結(jié)點時，在找到該結(jié)點時就進(jìn)行了刪除，這里不用考慮，具體看代碼。

這里有必要對各種情況的切換進(jìn)行說明，你可能會擔(dān)心調(diào)整紅黑樹時在這四種情況當(dāng)中一直來回切換而不能跳出，下面我們來對此進(jìn)行分析：

首先，進(jìn)入情況四后紅黑樹就一定調(diào)整結(jié)束了。其次，進(jìn)入情況三后，下次也一定會進(jìn)入情況四，紅黑樹的調(diào)整也會結(jié)束。所以情況三和情況四是沒有問題的，你們最糾結(jié)的只能是情況一和情況二了。

情況一又會切換為情況二、三、四，因此只要情況二能夠有辦法退出，那么所有情況就都能退出了。

在情況二當(dāng)中我們說，如果parent的顏色是紅色，那么我們將parent變?yōu)楹谏缶涂梢越Y(jié)束紅黑樹的調(diào)整，那會不會每次進(jìn)入情況二時parent的顏色都不是紅色，而一直是黑色的呢？

當(dāng)然有可能，但是我們?nèi)粢恢蓖线M(jìn)行調(diào)整時，那么總會調(diào)整到紅黑樹的根結(jié)點，當(dāng)調(diào)整到根結(jié)點后我們便不用進(jìn)行調(diào)整了，此時根結(jié)點雖然是黑色的，但是不影響，這僅僅意味著每條從根到葉子的路徑上包含的黑色結(jié)點的個數(shù)都減少了一個，此時也沒有破壞紅黑樹的性質(zhì)，也就完成了紅黑樹的調(diào)整，因此在調(diào)整過程中不會出現(xiàn)一直在這四種情況來回切換而不能跳出的問題。

第三步：進(jìn)行結(jié)點的實際刪除

在紅黑樹調(diào)整完畢后，我們就可以進(jìn)行結(jié)點的刪除了，刪除結(jié)點的方式很簡單，若待刪除結(jié)點有左孩子或右孩子，我們將其左孩子或右孩子連接到待刪除結(jié)點父結(jié)點的下面即可，之后便可以將待刪除結(jié)點刪除了。

代碼如下：

//刪除函數(shù)
bool Erase(const K& key)
{//用于遍歷二叉樹Node* parent = nullptr;Node* cur = _root;//用于標(biāo)記實際的待刪除結(jié)點及其父結(jié)點Node* delParentPos = nullptr;Node* delPos = nullptr;while (cur){if (key < cur->_kv.first) //所給key值小于當(dāng)前結(jié)點的key值{//往該結(jié)點的左子樹走parent = cur;cur = cur->_left;}else if (key > cur->_kv.first) //所給key值大于當(dāng)前結(jié)點的key值{//往該結(jié)點的右子樹走parent = cur;cur = cur->_right;}else //找到了待刪除結(jié)點{if (cur->_left == nullptr) //待刪除結(jié)點的左子樹為空{if (cur == _root) //待刪除結(jié)點是根結(jié)點{_root = _root->_right; //讓根結(jié)點的右子樹作為新的根結(jié)點if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根結(jié)點為黑色}delete cur; //刪除原根結(jié)點return true;}else{delParentPos = parent; //標(biāo)記實際刪除結(jié)點的父結(jié)點delPos = cur; //標(biāo)記實際刪除的結(jié)點}break; //進(jìn)行紅黑樹的調(diào)整以及結(jié)點的實際刪除}else if (cur->_right == nullptr) //待刪除結(jié)點的右子樹為空{if (cur == _root) //待刪除結(jié)點是根結(jié)點{_root = _root->_left; //讓根結(jié)點的左子樹作為新的根結(jié)點if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根結(jié)點為黑色}delete cur; //刪除原根結(jié)點return true;}else{delParentPos = parent; //標(biāo)記實際刪除結(jié)點的父結(jié)點delPos = cur; //標(biāo)記實際刪除的結(jié)點}break; //進(jìn)行紅黑樹的調(diào)整以及結(jié)點的實際刪除}else //待刪除結(jié)點的左右子樹均不為空{//替換法刪除//尋找待刪除結(jié)點右子樹當(dāng)中key值最小的結(jié)點作為實際刪除結(jié)點Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv.first = minRight->_kv.first; //將待刪除結(jié)點的key改為minRight的keycur->_kv.second = minRight->_kv.second; //將待刪除結(jié)點的value改為minRight的valuedelParentPos = minParent; //標(biāo)記實際刪除結(jié)點的父結(jié)點delPos = minRight; //標(biāo)記實際刪除的結(jié)點break; //進(jìn)行紅黑樹的調(diào)整以及結(jié)點的實際刪除}}}if (delPos == nullptr) //delPos沒有被修改過，說明沒有找到待刪除結(jié)點{return false;}//記錄待刪除結(jié)點及其父結(jié)點（用于后續(xù)實際刪除）Node* del = delPos;Node* delP = delParentPos;//調(diào)整紅黑樹if (delPos->_col == BLACK) //刪除的是黑色結(jié)點{if (delPos->_left) //待刪除結(jié)點有一個紅色的左孩子（不可能是黑色）{delPos->_left->_col = BLACK; //將這個紅色的左孩子變黑即可}else if (delPos->_right) //待刪除結(jié)點有一個紅色的右孩子（不可能是黑色）{delPos->_right->_col = BLACK; //將這個紅色的右孩子變黑即可}else //待刪除結(jié)點的左右均為空{while (delPos != _root) //可能一直調(diào)整到根結(jié)點{if (delPos == delParentPos->_left) //待刪除結(jié)點是其父結(jié)點的左孩子{Node* brother = delParentPos->_right; //兄弟結(jié)點是其父結(jié)點的右孩子//情況一：brother為紅色if (brother->_col == RED){delParentPos->_col = RED;brother->_col = BLACK;RotateL(delParentPos);//需要繼續(xù)處理brother = delParentPos->_right; //更新brother（否則在本循環(huán)中執(zhí)行其他情況的代碼會出錯）}//情況二：brother為黑色，且其左右孩子都是黑色結(jié)點或為空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要繼續(xù)處理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情況三：brother為黑色，且其左孩子是紅色結(jié)點，右孩子是黑色結(jié)點或為空if ((brother->_right == nullptr) || (brother->_right->_col == BLACK)){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);//需要繼續(xù)處理brother = delParentPos->_right; //更新brother（否則執(zhí)行下面情況四的代碼會出錯）}//情況四：brother為黑色，且其右孩子是紅色結(jié)點brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_right->_col = BLACK;RotateL(delParentPos);break; //情況四執(zhí)行完畢后調(diào)整一定結(jié)束}}else //delPos == delParentPos->_right //待刪除結(jié)點是其父結(jié)點的左孩子{Node* brother = delParentPos->_left; //兄弟結(jié)點是其父結(jié)點的左孩子//情況一：brother為紅色if (brother->_col == RED) //brother為紅色{delParentPos->_col = RED;brother->_col = BLACK;RotateR(delParentPos);//需要繼續(xù)處理brother = delParentPos->_left; //更新brother（否則在本循環(huán)中執(zhí)行其他情況的代碼會出錯）}//情況二：brother為黑色，且其左右孩子都是黑色結(jié)點或為空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要繼續(xù)處理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情況三：brother為黑色，且其右孩子是紅色結(jié)點，左孩子是黑色結(jié)點或為空if ((brother->_left == nullptr) || (brother->_left->_col == BLACK)){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);//需要繼續(xù)處理brother = delParentPos->_left; //更新brother（否則執(zhí)行下面情況四的代碼會出錯）}//情況四：brother為黑色，且其左孩子是紅色結(jié)點brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_left->_col = BLACK;RotateR(delParentPos);break; //情況四執(zhí)行完畢后調(diào)整一定結(jié)束}}}}}//進(jìn)行實際刪除if (del->_left == nullptr) //實際刪除結(jié)點的左子樹為空{if (del == delP->_left) //實際刪除結(jié)點是其父結(jié)點的左孩子{delP->_left = del->_right;if (del->_right)del->_right->_parent = delP;}else //實際刪除結(jié)點是其父結(jié)點的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}}else //實際刪除結(jié)點的右子樹為空{if (del == delP->_left) //實際刪除結(jié)點是其父結(jié)點的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = delP;}else //實際刪除結(jié)點是其父結(jié)點的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = delP;}}delete del; //實際刪除結(jié)點return true;
}

紅黑樹與AVL樹的比較

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪查改的時間復(fù)雜度都是O(logN)，但紅黑樹和AVL樹控制二叉樹平衡的方式不同：

AVL樹是通過控制左右高度差不超過1來實現(xiàn)二叉樹平衡的，實現(xiàn)的是二叉樹的嚴(yán)格平衡。
紅黑樹是通過控制結(jié)點的顏色，從而使得紅黑樹當(dāng)中最長可能路徑不超過最短可能路徑的2倍，實現(xiàn)的是近似平衡。
相對于AVL樹來說，紅黑樹降低了插入結(jié)點時需要進(jìn)行的旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，實際運(yùn)用時也大多用的是紅黑樹。

總結(jié)：

今天我們比較詳細(xì)地完成了紅黑樹的C++實現(xiàn)，了解了一些有關(guān)的底層原理。接下來，我們將進(jìn)行STL中 set、map、multiset、multimap類的學(xué)習(xí)。希望我的文章和講解能對大家的學(xué)習(xí)提供一些幫助。

當(dāng)然，本文仍有許多不足之處，歡迎各位小伙伴們隨時私信交流、批評指正！我們下期見~