前言

有人說設計出AVL樹的的人是個大牛，那寫紅黑樹（RBTree）的人就是天才！
上一篇文章，我們已經(jīng)學習了AVL樹，牛牛個人認為AVL樹已經(jīng)夠優(yōu)秀了，那讓我們一起探究一下，為什么紅黑樹比AVL樹的結(jié)構(gòu)還要優(yōu)秀吧！

一、紅黑樹的介紹

紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

紅黑樹，是一種自平衡的二叉查找樹，它的性質(zhì)比較復雜，但卻非常重要，常用于C++中的STL庫中的set、map等容器。紅黑樹的節(jié)點有兩種顏色：紅色（red）和黑色（black）。它具有如下五個性質(zhì)：

1. 每個節(jié)點是紅色或者黑色的。
2. 根節(jié)點是黑色的。
3. 每個葉子節(jié)點（這里特指最下面的空節(jié)點）是黑色的。
4. 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。（即：每條路徑上不能出現(xiàn)連續(xù)的紅結(jié)點）
5. 從任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點。

由于紅色結(jié)點的父親必須是黑色結(jié)點，并且每條路徑上的黑色結(jié)點的個數(shù)也必須相同，所以得到了紅黑樹最長路徑中節(jié)點個數(shù)不會超過最短路徑節(jié)點個數(shù)的兩倍

這也就決定了，紅黑樹的高度是log（n）級別的。
例如，下面這個就是紅黑樹

二、手撕紅黑樹

2.1 框架結(jié)構(gòu)分析

2.11 結(jié)點顏色

紅黑樹較于AVL樹，不在使用平衡因子，而是增設了顏色變量，這里我們可以枚舉出這兩種顏色，方便使用。

	enum Colour	//枚舉出顏色{RED,		//紅色BLACK		//黑色};

2.12 結(jié)點類

同AVL樹一樣，紅黑樹也是三叉鏈

	//結(jié)點類template<class K, class V>struct RBTreeNode{//指針域RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;	//數(shù)據(jù)域Colour _Col;RBTreeNode(const pair<K, V>& kv)//構(gòu)造函數(shù):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _Col(RED)				//注意這里，默認新構(gòu)造的結(jié)點是紅色的{}};

2.13 紅黑樹結(jié)構(gòu)

	//紅黑樹的結(jié)構(gòu)template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false//此版本紅黑樹對于重復元素，插入失敗bool Insert(const pair<K, V>& kv);// 搜索紅黑樹中是否存在值為data的節(jié)點。//存在返回該節(jié)點的地址，不存在則返回nullptrNode* Find(const pair<K, V>& data);// 獲取紅黑樹最左側(cè)節(jié)點Node* LeftMost();// 獲取紅黑樹最右側(cè)節(jié)點Node* RightMost();//（這里的玩法大家應該不陌生了）	int Height();//計算紅黑樹的高度bool IsValidRBTRee();// 檢測紅黑樹是否為有效的紅黑樹private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);int Height(Node* root);// 左單旋void RotateL(Node* pParent);// 右單旋void RotateR(Node* pParent);// 為了操作樹簡單起見：獲取根節(jié)點Node*& GetRoot();private:Node* _root = nullptr;};

2.2 接口實現(xiàn)

2.21 插入接口（重點）

本篇主要講解的部分就是紅黑樹的插入操作。

函數(shù)名 ：	insert
返回值	插入成功，返回true；插入失敗，返回false
形參	鍵值對

//插入函數(shù)
template<class K, class V>
bool RBTree<K, V>::Insert(const pair<K, V>& kv) {
}

（1）.如果是第一次插入，則插入的是根節(jié)點，則需要特殊處理，因為要給根節(jié)點root賦值。

在結(jié)點類中我們提到，在創(chuàng)建的新節(jié)點我們給與了默認顏色為RED（紅色），而紅黑樹的根節(jié)點必須是BLACK（黑色）的，這里一定要記得修改一下顏色。

//第一次插入if (_root == nullptr) {_root = new Node(kv);_root->_Col = BLACK;		//注意根節(jié)點一定是黑色的，默認構(gòu)造的新節(jié)點是紅色的，所以這里要改一下。return true;}

(2) 尋找插入位置
紅黑樹也是二叉搜索樹，學到這里，相信友友們在AVL樹和二叉搜索樹學習階段，已經(jīng)知道如何尋找插入位置。

	//尋找插入位置while (cur) {parent = cur;if (_root->_kv.first > kv.first) {cur = cur->_left;		//插入的值當前結(jié)點的值小，往左走}else if (_root->_kv.first < kv.first) {cur = cur->_right;		//插入的值當前結(jié)點的值大，往右走}else {return false;	//本篇實現(xiàn)的紅黑樹，對于重復值，插入失敗}}//判斷插入在左邊還是右邊cur = new Node(kv);if (kv.first < parent->_kv.first) {				//插入在左邊parent->_left = cur;}else {									//插入在右邊parent->_right = cur;}cur->_parent = parent;					//保證三叉鏈的關(guān)系

3.看uncle（叔叔）

叔叔（uncle）？這里我將當前結(jié)點的父親（parent）的兄弟稱為叔叔結(jié)點。

示例：

當我們新增一個結(jié)點時，默認新節(jié)點的顏色為RED，如果它的父親結(jié)點是黑色的，則不需要做任何調(diào)整，直接插入成功！

當父親結(jié)點是紅色的時候，則與新增結(jié)點一起，會構(gòu)成連續(xù)的紅色結(jié)點，此時需要調(diào)整。

調(diào)整規(guī)則主要看uncle叔叔結(jié)點。

情況1： 父親是爺爺?shù)淖?#xff0c;cur結(jié)點是父親的左。 （左左）

👻情況：叔叔存在且為紅
🔑調(diào)整方案： 變色+向上更新（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

👻情況：叔叔不存在，或者存在且為黑
🔑調(diào)整方案： 右旋+變色

（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

情況2： 父親是爺爺?shù)淖?#xff0c;cur結(jié)點是父親的右。 （左右）

👻情況：叔叔存在且為紅
🔑調(diào)整方案： 變色+向上更新
（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

👻情況：叔叔不存在，或者存在且為黑
🔑調(diào)整方案： 左右雙旋+變色

示例圖：

（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

情況3： 父親是爺爺?shù)挠?#xff0c;cur結(jié)點是父親的左。 （右左）

👻情況：叔叔存在且為紅
🔑調(diào)整方案： 變色+向上更新
這里不畫圖了，牛牛畫累了。

👻情況：叔叔不存在，或者存在且為黑
🔑調(diào)整方案： 右左雙旋+變色

（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

情況4： 父親是爺爺?shù)挠?#xff0c;cur結(jié)點是父親的左。 （右右）

👻情況：叔叔存在且為紅
🔑調(diào)整方案： 變色+向上更新
（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

👻情況：叔叔不存在，或者存在且為黑
🔑調(diào)整方案： 左旋+變色
（圖片為博主原創(chuàng)，請勿隨意轉(zhuǎn)發(fā)使用）

總結(jié)：
紅黑樹的插入主要看uncle
分為兩種情況：
（1）uncle存在且為紅
調(diào)整方案： 變色+繼續(xù)向上調(diào)整
（2）uncle不存在或者uncle存在且為黑
調(diào)整方案： 旋轉(zhuǎn)+變色

至于如何旋轉(zhuǎn)，因為紅黑樹沒有采用平衡因子的方式，所以我們采用判斷grandfather與parent 和 parent與cur的關(guān)系結(jié)構(gòu)來決定。
下圖是具體調(diào)整總結(jié)：

總代碼：

bool Insert(const T& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_Col = BLACK;		//注意根節(jié)點一定是黑色的，默認構(gòu)造的新節(jié)點是紅色的，所以這里要改一下。return true;}Node* cur = _root, * parent = nullptr;//尋找插入位置while (cur) {parent = cur;if (_root->_kv.first > kv.first) {cur = cur->_left;}else if (_root->_kv.first < kv.first) {cur = cur->_right;}else {return false;}}//判斷插入在左邊還是右邊cur = new Node(kv);if (kv.first < parent->_kv.first) {				//插入在左邊parent->_left = cur;}else {									//插入在右邊parent->_right = cur;}cur->_parent = parent;					//保證三叉鏈的關(guān)系//while (parent && parent->_Col == RED) {//爺爺結(jié)點Node* grandfather = parent->_parent;if (parent == grandfather->_left) {			//如果父親是爺爺?shù)淖蠛⒆?/span>Node* uncle = grandfather->_right;		//那么叔叔就是爺爺?shù)挠液⒆?/span>//叔叔存在且為紅if (uncle && uncle->_Col == RED) {//變色uncle->_Col=parent->_Col = BLACK;grandfather->_Col = RED;//繼續(xù)向上更新cur = grandfather;parent = grandfather->_parent;}else {									//叔叔不存在或者 存在且為黑if (cur == parent->_left) {			//			g//		p//cRotateR(grandfather);grandfather->_Col = RED;parent->_Col = BLACK;}else {//		g//	p//		cRotateL(parent);RotateR(grandfather);cur->_Col = BLACK;grandfather->_Col = RED;}break;	//此時最頂端的結(jié)點已經(jīng)變成黑色了，不需要繼續(xù)向上更新了。}}else {		// 如果父親是爺爺?shù)挠液⒆?/span>Node* uncle = grandfather->_left;		//那么叔叔就是爺爺?shù)淖蠛⒆?/span>//叔叔存在且為紅if (uncle && uncle->_Col == RED) {//變色uncle->_Col = parent->_Col = BLACK;grandfather->_Col = RED;//繼續(xù)向上更新cur = grandfather;parent = grandfather->_parent;}else {									//叔叔不存在或者 存在且為黑if (cur == parent->_left) {//	g//		p//	c//注意旋轉(zhuǎn)時的傳參RotateR(parent);RotateL(grandfather);grandfather->_Col = RED;cur->_Col = BLACK;}else {//	g//		p//			cRotateL(grandfather);		//注意旋轉(zhuǎn)時的傳參parent->_Col = BLACK;grandfather->_Col = RED;}break;	//此時最頂端的結(jié)點已經(jīng)變成黑色了，不需要繼續(xù)向上更新了。}}}_root->_Col = BLACK;		//最后根節(jié)點一定是黑的return true;}

2.22 最左側(cè)結(jié)點（LeftMost）

對于二叉搜索樹，如果我們按中序遍歷，則可以得到一個有序序列。
中序遍歷的首個結(jié)點： 最左側(cè)結(jié)點
中序遍歷的最后結(jié)點： 最右側(cè)結(jié)點

	// 獲取紅黑樹最左側(cè)節(jié)點template<class K, class V>typename RBTree<K, V>::Node* RBTree<K, V>::LeftMost() {Node* left_most = _root;while (left_most->left) {left_most = left_most->left;}return left_most;}

2.23 最右側(cè)結(jié)點（RightMost）

	// 獲取紅黑樹最右側(cè)節(jié)點template<class K, class V>typename RBTree<K, V>::Node* RBTree<K, V>::RightMost() {Node* right_most = _root;while (right_most->right) {right_most = right_most->left;}return right_most;}

2.24 檢測函數(shù)（次重點）

在實現(xiàn)紅黑樹時，也許我們會遇到各種問題，好不容易跑通代碼后，我們?nèi)睙o法判斷自己實現(xiàn)的紅黑樹是否正確，是否符合紅黑樹的規(guī)則。

此時，我們可以設計一個檢測函數(shù)，檢測實現(xiàn)的紅黑樹是否平衡。

1. 空樹也是紅黑樹
2. 根節(jié)點必須是紅黑樹
3. 我們可以設置一個“基準值”，基準值為紅黑樹一條路徑中的黑色結(jié)點的個數(shù)。
4. 遍歷每條紅黑樹的路徑，判斷紅黑樹結(jié)點的個數(shù)，是否與基準值相等。
5. 除此之外，出現(xiàn)連續(xù)兩個紅色結(jié)點則返回false。

// 檢測紅黑樹是否為有效的紅黑樹，注意：其內(nèi)部主要依靠_IsValidRBTRee函數(shù)檢測
template<class K, class V>
bool  RBTree<K, V>::IsValidRBTRee() {if (_root == nullptr)	//空樹也是紅黑樹return true;if (_root->_Col != BLACK)	//根節(jié)點必須是紅黑樹{return false;}// 基準值int pathBlack = 0;Node* cur = _root;while (cur){if (cur->_Col == BLACK)++pathBlack;cur = cur->_left;}_IsValidRBTRee(_root, 0, pathBlack);
}template<class K, class V>
bool RBTree<K, V>::_IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (pRoot == nullptr){if (blackCount != pathBlack)		//一條路徑走到底，也就是走到葉子結(jié)點以后，判斷這條路徑上的黑色結(jié)點個數(shù)（blackCount）是否與 設定的黑色結(jié)點個數(shù)相同（pathBlack）return false;return true;}if (pRoot->_Col == BLACK){++blackCount;}if (pRoot->_Col == RED && pRoot->_parent && pRoot->_parent->_Col == RED){cout << _root->_kv.first << "出現(xiàn)連續(xù)紅色節(jié)點" << endl;return false;}//遞歸訪問左右子樹return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
}

2.25 獲取根節(jié)點

	template<class K, class V>typename RBTree<K, V>::Node*& RBTree<K, V>::GetRoot() {return _root;}

2.25 獲取紅黑樹的高度

	template<class K, class V>int RBTree<K, V>::Height(){return Height(_root);}template<class K, class V>int RBTree<K, V>::Height(typename RBTree<K, V>::Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);	//計算左子樹的高度int rightHeight = Height(root->_right);	//計算右子樹的高度return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

2.26 find函數(shù)

template<class K, class T,>
typename RBTree<class K, class T, class Of_T>::Node* RBTree<class K, class T, class Of_T>::Find(const T& data) {Node* cur = _root;while (cur){if (data > cur->_data){cur = cur->_right;}else if (data < cur->_data){cur = cur->_left;}else return cur;}return nullptr;  // 找不到目標元素時返回nullptr
}

三、結(jié)語：

看完本篇文章，我們不難知道，對于插入操作，無論是紅黑樹還是avl樹，要維持對應的“平衡”，會進行沿路徑的更新，其中涉及大量的旋轉(zhuǎn)操作，而紅黑樹較于avl樹那種嚴格的高度差在-1到1之間，紅黑樹的平衡條件相對寬松，這也就大大減少了的為了維持平衡的大量旋轉(zhuǎn)操作，而且還能保證效率在log（N），這也就是為啥說紅黑樹較于avl樹更加優(yōu)秀。
你贊同這個觀點嗎？

后續(xù)牛牛會模擬實現(xiàn)map和set，會在那篇文章封裝紅黑樹，對紅黑樹進行改造，增加迭代器等功能。幫助友友們更加深入理解map和set容器。