一、紅黑樹的概念

紅黑樹是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是 Red 或 Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，這句話換個意思就是：紅黑樹中最長路徑不超過最短路徑的 2 倍。因而是接近平衡的，而 AVL 樹是嚴格平衡的，這就導致，紅黑樹的高度會比 AVL 樹高一些，但是效率并不會比 AVL 樹差。

二、紅黑樹的性質(zhì)

• 每個結點不是紅色就是黑色。

• 根節(jié)點是黑色。

• 如果一個結點是紅色，則它的兩個孩子結點必須是黑色的。

• 對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數(shù)目的黑色結點。

• 每個 NIL 葉子結點都是黑色的（此處的葉子結點指的是空節(jié)點）。

小Tips：第三點決定了一顆紅黑樹的任何路徑?jīng)]有連續(xù)的紅色結點。在紅黑樹中計算路徑一定是計算到 NIL 結點。一顆紅黑樹中的最短路徑是全為黑結點的路徑，最長路徑是一黑一紅相間的路徑。任意一條路徑上黑色結點的占比一定是大于等于 $1/2$ 的。這就決定了，紅黑樹中其最長路徑中結點個數(shù)不會超過最短路徑結點個數(shù)的兩倍。

三、紅黑樹結點的定義

//紅黑樹的結點
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(color)
	{}

	pair<K, V> _kv;//結點中存的值
	RBTreeNode<K, V>* _left;//結點的左孩子
	RBTreeNode<K, V>* _right;//結點的右孩子
	RBTreeNode<K, V>* _parent;//結點的父親
	Color _col;//結點的顏色
};

小Tips：新節(jié)點默認顏色是 RED。這是因為，如果新插入結點的顏色是 BLACK，那意味著當前路徑上新增了一個黑色結點，為了保證二叉樹的第四條性質(zhì)，我們要對這顆紅黑樹其他的所有路徑進行檢查，可見新插入結點如果默認是 BLACK，會存在著牽一發(fā)而動全身的影響。而讓新插入結點默認是 RED 則不會出現(xiàn)這樣的結果。假如新插入結點的 parent 恰好是 BLACK，那這次插入就沒有什么問題。如果新插入結點是 parent 是 RED，此時需要對這顆紅黑樹稍作調(diào)整。

四、紅黑樹的插入操作

紅黑樹是在二叉搜索樹的基礎上加上平衡限制條件，因此紅黑樹的插入可以分為兩步：

• 按照二叉搜索樹的規(guī)則插入結點。

• 檢測新節(jié)點插入后，紅黑樹的性質(zhì)是否遭到破壞。

因為新結點的默認顏色是 RED，因此：如果其雙親結點的顏色是 BLACK，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；但是當新插入節(jié)點的雙親結點顏色為 RED 時，就違反了性質(zhì)三不能有連在一起的紅色結點，此時需要對紅黑樹分情況來討論：

約定：cur為當前結點，parent 為父結點，grandp 為祖父結點，uncle 為叔叔結點。如果 parent 為紅那 grandp 一定為黑。所以當前唯一不確定的就是 uncle，主要分以下三種情況

4.1 情況一：uncle 存在且為紅

小Tips：此處看到的樹，可能是一顆完整的樹，也可能是一顆子樹。

解決方式：將 parent 和 uncle 改為黑，grandp 改成紅。然后把 grandp 當成 cur，繼續(xù)向上調(diào)整。

• 如果 grandp 是根結點，將 grandp 再改成黑色，本次插入就算結束。

• 如果 grandp 是子樹，則其一定也有雙親，且 grandp 的雙親如果是紅色，需要繼續(xù)向上調(diào)整。

4.2 情況二：uncle 不存在

如果 uncle 結點不存在，則 cur 一定是新插入結點，因為如果 cur 不是新插入結點，則 cur 和 parent 一定有一個結點的顏色是黑色，就不滿足性質(zhì)四：每條路徑黑色結點個數(shù)相同。

解決方法：直接進行旋轉(zhuǎn)即可。

4.3 情況三：uncle 存在且為黑

叔叔存在且為黑，那么 cur 一定不是新插入的結點，并且 cur 結點原來的顏色一定是黑色，現(xiàn)在看到是紅色的原因是因為 cur 的子樹在調(diào)整的過程中將 cur 結點的顏色由黑色改成了紅色。

4.4 插入完整源碼

public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;//插入成功
		}

		//找插入位置
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (kv.first < cur->_kv.first)//小于往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)//大于往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else//相等插入不了
			{
				return false;
			}
		}

		//找到待插入位置了，進行插入
		cur = new Node(kv);
		cur->_col = RED;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		cur->_parent = parent;

		//檢測新結點插入后，紅黑樹的性質(zhì)是否遭到破壞
		while (parent && parent->_col == RED)
		{
			Node* grandp = parent->_parent;
			if (parent == grandp->_left)
			{
				Node* uncle = grandp->_right;
				if (uncle && uncle->_col == RED)//叔叔存在且為紅
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandp->_col = RED;

					//繼續(xù)向上處理
					cur = grandp;
					parent = cur->_parent;
				}
				else //uncle不存在或者存在為黑
				{
					if (cur == parent->_left)
					{
						RotateR(grandp);
						parent->_col = BLACK;//parent當了根
						grandp->_col = RED;
					}
					else if (cur == parent->_right)
					{
						RotateLR(grandp);
						cur->_col = BLACK;//cur當了根節(jié)點
						grandp->_col = RED;
					}

					break;
				}
			}
			else if (parent == grandp->_right)
			{
				Node* uncle = grandp->_left;
				if (uncle && uncle->_col == RED)//叔叔存在且為紅
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandp->_col = RED;

					//繼續(xù)向上處理
					cur = grandp;
					parent = cur->_parent;
				}
				else //uncle不存在或者存在為黑
				{
					if (cur == parent->_right)
					{
						RotateL(grandp);
						parent->_col = BLACK;//parent當了根
						grandp->_col = RED;
					}
					else if (cur == parent->_left)
					{
						RotateRL(grandp);
						cur->_col = BLACK;//cur當了根節(jié)點
						grandp->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;//根結點始終變黑
		return true;
	}
private:
	//左單旋
	void RotateL(Node* parent)
	{
		++_rotatecount;
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		cur->_left = parent;

		if (curleft)
		{
			curleft->_parent = parent;
		}

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}

	}

	//右單旋
	void RotateR(Node* parent)
	{
		++_rotatecount;
		Node* cur = parent->_left;
		Node* curright = cur->_right;//此時的情況是curright比cur大，比parent小

		parent->_left = curright;
		cur->_right = parent;

		if (curright)
		{
			curright->_parent = parent;
		}

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

		if (ppnode)
		{
			cur->_parent = ppnode;
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
		}
		else
		{
			_root = cur;
			cur->_parent = nullptr;
		}
	}

	//右左雙旋
	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		RotateR(parent->_right);
		RotateL(parent);

	}

	//左右雙旋
	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		RotateL(cur);
		RotateR(parent);

	}

五、紅黑樹的驗證

紅黑樹的檢測分為兩步：

• 檢測其是否滿足二叉搜索樹（中序遍歷是否為有序序列）。

• 檢測其是否滿足紅黑樹的性質(zhì)（主要是性質(zhì)三和性質(zhì)四）。

public:
	bool Isblance()
	{
		if (_root == nullptr)
			return true;

		//根節(jié)點如果不是黑色說明就不是紅黑樹
		if (_root->_col != BLACK)
		{
			return false;
		}

		//計算紅黑樹中任意一條路徑上黑色結點的個數(shù)作為一個基準值
		Node* cur = _root;
		int count = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++count;
			}
			cur = cur->_left;
		}

		return CheckColour(_root, 0, count);
	}
private:
	//檢查顏色
	bool CheckColour(Node* root, int blacknum, int stand)
	{
		if (root == nullptr)
		{
			//到這里說明一條路徑結束，那么這條路徑上的黑色結點數(shù)也一定統(tǒng)計出來了
			if (blacknum != stand)
			{
				cout << "當前路徑上黑色結點的個數(shù)有問題" << endl;
				return false;
			}

			return true;
		}

		//檢查是否出現(xiàn)連續(xù)的紅色結點
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << ":為紅色節(jié)點，并且孩子結點也是紅色" << endl;
		}

		//統(tǒng)計一條路徑上黑色結點個數(shù)
		if (root->_col == BLACK)
		{
			++blacknum;
		}

		return CheckColour(root->_left, blacknum, stand) && CheckColour(root->_right, blacknum, stand);
	}	

六、紅黑樹與 AVL 樹的比較

紅黑樹和 AVL 樹都是高效的平衡二叉樹，增刪查改的時間復雜度都是 $O(log{2}^N)$，紅黑樹不追求絕對平衡，其只需要保證最長路徑不超過最短路徑的 2 倍，相對而言，降低了插入過程中旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進行增刪查改的結構中性能比 AVL 樹更優(yōu)，而且紅黑樹實現(xiàn)比較簡單，所以實際運用中紅黑樹更多。紅黑樹主要會應用在以下幾個地方：

• C++ STL 庫----map、set、mutilmap、mutilset。

• Java 庫。

• Linux 內(nèi)核。

• 其它一些庫。

七、結語

今天的分享到這里就結束啦！如果覺得文章還不錯的話，可以三連支持一下，春人的主頁還有很多有趣的文章，歡迎小伙伴們前去點評，您的支持就是春人前進的動力！

文章來源地址http://www.zghlxwxcb.cn/news/detail-713413.html

到了這里，關于【C++雜貨鋪】一文帶你走進RBTree的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！