什么是紅黑樹

????????紅黑樹是在二叉搜索樹的基礎上添加顏色，通過對任何一條路徑的顏色的限制，確保紅黑樹的任何一條路徑不會超過其他路徑的兩倍，是一棵近似平衡的樹。

? ? ? ? 紅黑樹的節(jié)點不是紅色就是黑色，其節(jié)點的排列除了需要按二插搜索樹的規(guī)則來插入之外，還添加了以下規(guī)則：

• 每個節(jié)點不是紅色就是黑色
• 根節(jié)點為黑色
• 如果一個節(jié)點為紅色，則它的子節(jié)點都是黑色
• 對于每個節(jié)點，從該節(jié)點到其每個后代葉節(jié)點的簡單路徑上，黑色節(jié)點的個數(shù)都是相同的
• 每個葉子節(jié)點都是黑色的（空節(jié)點也是黑色的）

從規(guī)則上可以看出，紅黑樹的最短路徑應該都是黑色節(jié)點，最長路徑應該是黑紅節(jié)點相間插入。

而因為從根到葉節(jié)點的每條路徑上的黑色節(jié)點個數(shù)都應相等，因此最長路徑最多到最短路徑的兩倍

紅黑樹的實現(xiàn)

紅黑樹節(jié)點實現(xiàn)

與AVL樹不同，紅黑樹沒有平衡因子，而是多了一個表示顏色的成員。

enum Color
{
	RED,
	BLACK,
};
template<class K,class V>
struct RBNode {
	pair<K, V> _kv;
	RBNode<K, V>* _left;
	RBNode<K, V>* _right;
	RBNode<K, V>* _parent;
	Color _col;
	RBNode(pair<K, V> kv)
		:_kv(kv),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)
	{
	}
};

紅黑樹的插入實現(xiàn)

????????由于紅黑樹的查找和打印和二叉搜索樹都一樣，因此這里我們直接學習插入和刪除。

????????根據(jù)紅黑樹的性質 3 和性質 4 ，當我們插入一個新節(jié)點時，如果新節(jié)點是黑色，那么它一定違反了性質 4，而如果新節(jié)點是紅色，那么它有可能違反性質 3 ，有可能不會，需要根據(jù)插入位置的父節(jié)點的顏色來判斷。

? ? ? ? 因此我們設置插入的新節(jié)點都為紅色，如果違反了性質 3，就要去修復紅黑樹。

? ? ? ? 當父節(jié)點為黑色，就不需要修復，而如果是紅色，則需要進行修復。

? ? ? ? 我們規(guī)定 cur 為插入的新節(jié)點，p 為父親節(jié)點，g 為祖父節(jié)點，u為叔叔節(jié)點

cur為紅，p為紅，g為黑，u為紅

這種情況無疑是違反了性質 3 的，因此需要修復。

因此我們需要將 p 的顏色變?yōu)楹冢沁@樣 g 的左路徑就多出了一個黑節(jié)點，就破壞了性質 4；

因此我們還需要將 u 的顏色也變黑，這樣 g 的左右路徑的黑色節(jié)點就相同了。

但是如果 g 節(jié)點是一棵子樹的話，那么 g 的父節(jié)點的左右路徑的黑色節(jié)點就不同了，因此我們需要將 g 變紅。

因此對于這種情況，我們的操作是：p變黑，u變黑，g變紅。

僅僅這樣還未結束：g 的父節(jié)點可能也是紅節(jié)點，因此需要將 cur 指向 g，來繼續(xù)向上遍歷。

cur為紅，p為紅，g為紅，u不存在/為黑

u不存在：u不存在時，表明 cur 是新增節(jié)點，因為若cur不是新增節(jié)點，則cur和p一定有一個為黑，就不符合性質4了

u存在：若u存在，則 cur 原本的顏色一定為黑，說明這個情況是由情況一（上面的情況）演變而來的。

面對這種情況，我們需要旋轉來解決。

cur 是 p 的左孩子，p 是 g 的左孩子，則右旋

cur 是 p 的右孩子，p 是 g 的右孩子，則左旋

旋轉之后，p變黑色，g變紅色

這樣子乍一看好像 p 到 u 的路徑多一個黑節(jié)點，但這是分情況而言的。

如果 u 不存在，那么這樣 p 的左右路徑的黑節(jié)點個數(shù)都一樣。

若u存在，那么這種情況就是由情況1演變而來，?cur 就是情況一的 g 節(jié)點，其左右子樹都有一個黑節(jié)點，因此還是平衡的。

cur為紅，p為紅，g為紅，u不存在/為黑

這種情況和情況二類似，只是 cur 所在位置不同。

u不存在說明cur是新節(jié)點，u存在則說明cur不是新節(jié)點，該情況由情況一轉變而來。

這種情況就需要雙旋出場了。

?cur 在 p 的右邊，p 在 g 的左邊，需要先對 p 一個左旋，再對 g 一個右旋

?cur 在 p 的左邊，p 在 g 的右邊，需要先對 p 一個右旋，再對 g 一個左旋

然后 cur?變黑，g變紅

?

這樣也平衡了。

bool Insert(const pair<K, V> kv)
{
	if (_root == nullptr)
	{
		pNode cur = new Node(kv);
		_root = cur;
		_root->_col = BLACK;
		return true;
	}
	pNode cur = _root;
	pNode parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	//這個時候cur應該到空了，parent指向下一個
	cur = new Node(kv);
	cur->_col = RED;
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	while (parent && parent->_col == RED)
	{
		pNode grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			pNode uncle = grandfather->_right;
			//情況一 cur紅 p 紅 g黑 u存在且為紅
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else
			{
				//u不存在或者為黑
				if (cur == parent->_left)
				{
					//情況二 cur 在parent 的左邊
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else
				{
					//情況三 cur 在 parent 的右邊
					RotateL(parent);
					RotateR(grandfather);
					grandfather->_col = RED;
					cur->_col = BLACK;
				}
			}
		}
		else
		{
			pNode uncle = grandfather->_left;
			//情況一 cur紅 p 紅 g黑 u存在且為紅
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else
			{
				//u不存在或者為黑
				if (cur == parent->_left)
				{
					//情況三 cur 在parent 的左邊
					RotateR(parent);
					RotateL(grandfather);
					grandfather->_col = RED;
					cur->_col = BLACK;
				}
				else
				{
					//情況三 cur 在 parent 的右邊
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
			}
		}
	}
	_root->_col = BLACK;
}

紅黑樹的刪除實現(xiàn)

? ? ? ? 和所有二叉搜索樹的刪除一樣，紅黑樹的刪除也分為三種情況：為葉子節(jié)點，有一個節(jié)點不為空，都不為空。

? ? ? ? 我們約定刪除節(jié)點為 n，父節(jié)點為 p，兄弟節(jié)點為 s，cur 的子節(jié)點為 k。

? ? ? ? 當cur的左右不為空時，我們應該去找 cur 的前驅或者后驅節(jié)點，這里我們使用后驅節(jié)點，將 cur 的值和找到的節(jié)點替換，然后再去刪除這個后驅節(jié)點。而我們發(fā)現(xiàn)，當我們找到這個后驅節(jié)點時，這個后驅節(jié)點的右邊一定要么只有一個節(jié)點，且顏色為紅，要么沒有節(jié)點，否則就會違反性質3或者4.

? ? ? ? 也就是說：左右不為空的情況可以轉化成另外兩種情況，而轉化后cur的顏色為黑時，我們才需要去修復紅黑樹，為紅時可以直接刪除。

s為紅色，n是p的左孩子（或者右孩子）

? ? ? ? 這種情況下，p一定為黑色。

解決方法：首先p變紅， b邊黑，cur為p的左節(jié)點，就左旋，cur為p的右節(jié)點，就右旋

這種情況是在cur節(jié)點上添加了一個紅色節(jié)點，但是cur刪除后從 p 到cur還是會少一個黑色節(jié)點，因此需要再對cur進行檢索。

p，s及s的孩子都為黑

解決方法：將s變?yōu)榧t色?

這種情況下，由于p到cur的路徑一定會少一個黑色節(jié)點，因此我們需要將b變?yōu)榧t，這樣就能保證p的左右子樹的黑色節(jié)點數(shù)量相同。?

但是這樣 g 到 p 節(jié)點的路徑的黑色節(jié)點數(shù)量就會減一，因此需要從 p 往上再修復。

p為紅，s以及s的孩子都為黑

解決方法：將p變?yōu)楹?，s變?yōu)榧t?

這樣無論是從 g 到 p 的路徑的黑色節(jié)點個數(shù)還是 p 的左右黑色節(jié)點的個數(shù)都沒有變化,而這種情況實際上就是情況一演變而來的。

p為任意顏色，s為黑，s的右孩子為紅，左孩子任意，n為左

注意：這種情況也有可能是 n為右孩子，s為黑，s的左孩子為紅，右孩子任意，是相對的。

二者的解決方法也是相對的。

解決方法：sr（sl）變?yōu)楹?，s變?yōu)閜的顏色，p變?yōu)楹谏?，然后p左旋?（右旋）

通過這種方法就完成了紅黑樹的修復，平衡。?

p任意色，s為黑，n為p的左孩子，sl為紅，sr為黑?

?和之前類似，這種情況也有相對的：n為右還在，sr為紅，sl為黑。

解決方法：sl（sr）變黑，s變紅，然后s右旋（左旋）

這種情況就會轉化成情況四，然后再通過情況四的方法修復。

下面貼上代碼。

void Modify_Erase(pNode cur)
{
	while (cur->_col == BLACK)
	{
		pNode parent = cur->_parent;
		if (parent->_left == cur)
		{
			pNode rnode = parent->_right;
			//情況一 兄弟節(jié)點為紅
			if (rnode->_col == RED)
			{
				//首先左旋然后將父節(jié)點和兄弟節(jié)點變色
				parent->_col = RED;
				rnode->_col = BLACK;
				RotateL(parent);
				//這樣會轉換成情況三: cur 的父節(jié)點為紅，兄弟為黑s
			}
			else if (rnode->_col == BLACK && parent->_col == BLACK &&((rnode->_left && rnode->_left->_col == BLACK )&& (rnode->_right && rnode->_right->_col == BLACK)))
			{
				rnode->_col = RED;
				//這樣就會轉化為情節(jié)一
			}
			else if (parent->_col == RED && rnode->_left && rnode->_left->_col == BLACK && rnode->_right && rnode->_right->_col == BLACK)
			{
				parent->_col = BLACK;
				rnode->_col = RED;
				//情況三 : 父節(jié)點為紅（兄弟節(jié)點一定為黑),且兄弟節(jié)點的子節(jié)點都為黑
				//將父節(jié)點的顏色變?yōu)楹冢值芄?jié)點變?yōu)榧t，那么刪除cur后依舊符合紅黑樹
				return;
			}
			else if (rnode->_col == BLACK && rnode->_right && rnode->_right->_col == RED)
			{
				rnode->_right->_col = BLACK;
				rnode->_col = parent->_col;
				parent->_col = BLACK;
				RotateL(parent);
				return;
			}
			else if (rnode->_col == BLACK && rnode->_left && rnode->_left->_col == RED && rnode->_right && rnode->_right->_col == BLACK)
			{
				rnode->_col = RED;
				rnode->_left->_col = BLACK;
				RotateR(rnode);
				//轉換為情況四
			}

		}
		else
		{
			pNode lnode = parent->_left;
			//情況一 兄弟節(jié)點為紅
			if (lnode->_col == RED)
			{
				//首先右旋然后將父節(jié)點和兄弟節(jié)點變色
				parent->_col = RED;
				lnode->_col = BLACK;
				RotateR(parent);
				//這樣會轉換成情況三: cur 的父節(jié)點為紅，兄弟為黑s
			}
			else if (lnode->_col == BLACK && parent->_col == BLACK && ((lnode->_left && lnode->_left->_col == BLACK) && (lnode->_right && lnode->_right->_col == BLACK)))
			{
				lnode->_col = RED;
				//這樣就會轉化為情節(jié)一
			}
			else if (parent->_col == RED && lnode->_left && lnode->_left->_col == BLACK && lnode->_right && lnode->_right->_col == BLACK)
			{
				parent->_col = BLACK;
				lnode->_col = RED;
				//情況三 : 父節(jié)點為紅（兄弟節(jié)點一定為黑),且兄弟節(jié)點的子節(jié)點都為黑
				//將父節(jié)點的顏色變?yōu)楹冢值芄?jié)點變?yōu)榧t，那么刪除cur后依舊符合紅黑樹
				return;
			}
			else if (lnode->_col == BLACK && lnode->_right && lnode->_right->_col == RED)
			{
				lnode->_left->_col = BLACK;
				lnode->_col = parent->_col;
				parent->_col = BLACK;
				RotateR(parent);
				return;
			}
			else if (lnode->_col == BLACK && lnode->_left && lnode->_left->_col == BLACK && lnode->_right && lnode->_right->_col == RED)
			{
				lnode->_col = RED;
				lnode->_right->_col = BLACK;
				RotateR(lnode);
				//轉換為情況四
			}
		}
	}
}

bool Erase(const pair<K, V>& val)
{
	pNode cur = Find(val);
	if (cur == nullptr)
	{
		return true;
	}
	//當被刪除節(jié)點的左右子樹不為空，則找到最小右節(jié)點后交換二者的值
	//轉換成只有一個子樹不為空或者都為空的情況
	if (cur->_left && cur->_right)
	{
		pNode parent = cur;
		pNode minright = cur->_right;
		while (minright->_left)
		{
			parent = minright;
			minright = minright->_left;
		}
		//找到最小右節(jié)點后，交換二者的值
		cur->_kv = minright->_kv;
		cur = minright;
	}
	pNode kid = cur->_left == nullptr ? cur->_right : cur->_left;
	if (kid != nullptr)
	{
		//子樹有一邊不為空
		//只要刪除節(jié)點有一邊不為空，就直接把不為空的那一邊連接起來
		//并且直接設為黑
		kid->_parent = cur->_parent;
		if (cur == _root)
		{
			_root = kid;
		}
		else if (cur->_parent->_left == cur)
		{
			cur->_parent->_left = kid;
		}
		else if (cur->_parent->_right == cur)
		{
			cur->_parent->_right = kid;
		}
		kid->_col = BLACK;
		delete cur;
	}
	else if (kid == nullptr)
	{
		//當節(jié)點為葉子節(jié)點時，就需要修改
		Modify_Erase(cur);
		if (cur->_parent->_left == cur)
			cur->_parent->_left = nullptr;
		else
			cur->_parent->_right = nullptr;
	}
	return true;
}

這里修復的前提是 n 為黑且 n 的左右節(jié)點為空。

如果n不為空且為黑，它的孩子一定是紅色，我們可以直接刪除 n 然后把 p 連接到 n 的孩子，并修改孩子的顏色，這樣依舊平衡。

而如果n為紅，則一定為葉子節(jié)點，否則就會不平衡。

而以上5種情況是會相互之間轉化的，因此也許 n 具有左右節(jié)點。

紅黑樹的驗證

和AVL樹一樣，都是需要遞歸檢查是否都符合紅黑樹的性質。

我們先計算從根節(jié)點都葉子節(jié)點的某一條路徑的黑色節(jié)點數(shù)，然后進行遞歸檢查。

如果到了空節(jié)點發(fā)現(xiàn)黑色節(jié)點數(shù)都不相等，就返回false，否則返回true.

	bool _IsRBTree(pNode cur, int k, int blacknum)
	{
		if (cur == nullptr)
		{
			if (k != blacknum)
			{
				return false;
			}
			return true;
		}
		if (cur->_col == BLACK)
		{
			k++;
		}
		pNode parent = cur->_parent;
		if (parent && parent->_col == RED && cur->_col == RED)
		{
			cout << "違反性質三 ：兩個相連的紅色節(jié)點" << endl;
			return false;
		}
		return _IsRBTree(cur->_left, k, blacknum) && _IsRBTree(cur->_right, k, blacknum);
	}	
bool IsRBTree()
	{
		pNode cur = _root;
		if (cur == nullptr)
		{
			return true;
		}
		if (cur->_col == RED)
		{
			cout << "違反性質二 ： 根節(jié)點必須為黑色" << endl;
			return false;
		}
		int blacknum = 0;
		pNode tmp = cur;
		while (tmp)
		{
			if (tmp->_col == BLACK)
			{
				blacknum++;
			}
			tmp = tmp->_left;
		}
		int k = 0;
		return _IsRBTree(cur, k, blacknum);
	}

總結

紅黑樹相比于AVL樹并不注重完全平衡，而是近似平衡，但因為AVL樹需要不停的旋轉來保持自身的結構，紅黑樹的增刪結構相比于AVL樹更優(yōu)，而且紅黑樹的實現(xiàn)更為簡單，因此一般都使用紅黑樹。

二者的增刪查改復雜度都是 O(logN)級別的。文章來源地址http://www.zghlxwxcb.cn/news/detail-780336.html

到了這里，關于紅黑樹的了解以及代碼實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！