紅黑樹(shù)的實(shí)現(xiàn)會(huì)比AVL簡(jiǎn)單-.-

判斷是否是AVL樹(shù)

上一篇文章我們?cè)敿?xì)介紹了AVL樹(shù)并且實(shí)現(xiàn)了AVL樹(shù)，這篇文章我們將在前言中引入判斷是否是AVL樹(shù)的方法，然后我們就進(jìn)入紅黑樹(shù)的實(shí)現(xiàn)，如果是能自己實(shí)現(xiàn)AVL樹(shù)的同學(xué)那么實(shí)現(xiàn)起紅黑樹(shù)就會(huì)非常簡(jiǎn)單了，下面我們介紹一下如何判斷AVL樹(shù)：

首先AVL樹(shù)本質(zhì)是根據(jù)平衡因子的調(diào)節(jié)來(lái)實(shí)現(xiàn)平衡，所以我們可以根據(jù)平衡因子來(lái)判斷，代碼如下：

        bool IsBalance()
		{
			return _IsBalance(_root);
		}

int _Height(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			return _Height(root->_left) > _Height(root->_right) ? _Height(root->_left) + 1 : _Height(root->_right) + 1;
		}

bool _IsBalance(Node* root)
		{
			if (root == nullptr)
			{
				return true;
			}
			int left = _Height(root->_left);
			int right = _Height(root->_right);
			if (abs(right - left) >= 2)
			{
				cout << root->_kv.first << "節(jié)點(diǎn)的高度差大于等于2" << endl;
				return false;
			}
			if (right - left != root->_bf)
			{
				cout << root->_kv.first << "節(jié)點(diǎn)的平衡因子錯(cuò)誤" << endl;
				return false;
			}
			return _IsBalance(root->_left) && _IsBalance(root->_right);
		}

?如上代碼所示，我們先寫(xiě)了一個(gè)求樹(shù)高度的函數(shù)，因?yàn)榈葧?huì)要判斷每個(gè)節(jié)點(diǎn)的左右高度差，然后我們先求出整棵樹(shù)的左右子樹(shù)的高度，然后判斷左右子樹(shù)高度差是否小于2，如果不小于則說(shuō)明不是AVL樹(shù)，然后再判斷平衡因子，平衡因子是等于右子樹(shù)高度減去左子樹(shù)高度，如果右樹(shù)高度減去左樹(shù)高度不等于平衡因子大小則說(shuō)明平衡因子錯(cuò)了也不是AVL樹(shù)，然后我們?cè)俜謩e判斷每顆子樹(shù)即可。下面我們跑一下測(cè)試：

void test1()
{
	/*int a[] = { 16,3,7,11,9,26,18,14,15 };*/
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	AVLTree::AVLTree<int, int> at;
	for (auto& e : a)
	{
		//打條件斷點(diǎn)
		/*if (e == 14)
		{
			int x = 0;
		}*/
		at.insert(make_pair(e, e));
		cout << e << "插入：" << at.IsBalance() << endl;
	}
	at.Inorder();
	cout << endl;
	cout << at.IsBalance() << endl;
}

?上面條件斷點(diǎn)的方式大家可以學(xué)一下，當(dāng)數(shù)據(jù)量很多需要調(diào)試的時(shí)候，比如上圖中的數(shù)據(jù)只有插入14的時(shí)候才會(huì)引發(fā)旋轉(zhuǎn)，所以我們可以單獨(dú)在14這個(gè)節(jié)點(diǎn)測(cè)一下旋轉(zhuǎn)是否正確，只需要寫(xiě)個(gè)if語(yǔ)句然后在語(yǔ)句中隨便寫(xiě)一個(gè)代碼，因?yàn)槿绻Z(yǔ)句為空是打不上斷點(diǎn)的，如下圖：

?下面在跑一下隨機(jī)數(shù)測(cè)試：

void test2()
{
	srand(time(0));
	const size_t N = 100000;
	AVLTree::AVLTree<int, int> at;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand();
		at.insert(make_pair(x, x));
	}
	cout << at.IsBalance() << endl;
}

?可以看到也是沒(méi)有問(wèn)題的，以上AVL樹(shù)就結(jié)束了，下面我們就開(kāi)始紅黑樹(shù)的學(xué)習(xí)。

一、紅黑樹(shù)

紅黑樹(shù)的性質(zhì)：

1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色。

2. 根節(jié)點(diǎn)是黑色的。

二、紅黑樹(shù)的實(shí)現(xiàn)

紅黑樹(shù)與AVL數(shù)有很多相似的地方，所以我們直接實(shí)現(xiàn)紅黑樹(shù)不同的地方即可：

首先我們先將節(jié)點(diǎn)寫(xiě)出來(lái)：

#include <assert.h>
#include <iostream>
using namespace std;

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

	}
};

?與AVL樹(shù)不同的是紅黑樹(shù)多了一個(gè)顏色，所以我們用一個(gè)枚舉來(lái)控制顏色，下面我們先將紅黑樹(shù)插入與AVL樹(shù)插入差不多相同的地方寫(xiě)好：

template <class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			//根節(jié)點(diǎn)必須為黑色
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		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 = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//開(kāi)始紅黑樹(shù)

	}

private:
	Node* _root = nullptr;
};

?下面我們分析紅黑樹(shù)的插入：

?從上圖中我們可以看到，當(dāng)新增節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色時(shí)，不會(huì)違反任何規(guī)則，所以當(dāng)新增節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色時(shí)不用調(diào)整直接插入成功了。

?如果是上圖這樣的情況當(dāng)新增節(jié)點(diǎn)的父親是紅色該怎么辦呢？我們可以看到這樣是會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)的違反了規(guī)則3，當(dāng)出現(xiàn)這樣的情況，我們給出的方法是將parent節(jié)點(diǎn)和uncle節(jié)點(diǎn)改為黑色，然后將grandfather改為紅色，如下圖：

?如上圖當(dāng)我們修改完parent,uncle,grandfather的顏色后發(fā)現(xiàn)grandfather節(jié)點(diǎn)和其父節(jié)點(diǎn)也出現(xiàn)了連續(xù)的紅色，所以這種情況是需要向上調(diào)整的，讓cur變成grandfather即可：

?如上圖所示，向上調(diào)整完成后如果grandfather是根節(jié)點(diǎn)我們還需要將根節(jié)點(diǎn)修改為黑色，然后我們發(fā)現(xiàn)修改完成后每條路徑的黑色節(jié)點(diǎn)數(shù)量都是相同的并且一個(gè)紅色節(jié)點(diǎn)都有兩個(gè)黑色節(jié)點(diǎn)，下面我們完成代碼：

cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//開(kāi)始紅黑樹(shù)
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//向上調(diào)整
					cur = grandfather;
					parent = cur->_parent;
				}
			}
		}
	}

?這里我們可以看到當(dāng)parent在祖父的左邊那么uncle就是祖父的右邊所以要分兩種情況，parent在祖父的左邊是一種情況，parent在祖父的右邊是一種情況。上圖我們演示的情況是當(dāng)叔叔存在并且為紅色我們的解決方案，下面看看當(dāng)叔叔節(jié)點(diǎn)不存在或者叔叔節(jié)點(diǎn)為黑色的解決方案：

?我們可以看到當(dāng)出現(xiàn)叔叔是黑色的情況是需要旋轉(zhuǎn)的，如果新增節(jié)點(diǎn)和parent和grandfather在一條線(xiàn)上的話(huà)那就需要先對(duì)grandfather節(jié)點(diǎn)進(jìn)行單旋，然后將parent節(jié)點(diǎn)變成黑色，grandfather節(jié)點(diǎn)變成紅色。

這里再次說(shuō)明：

uncle的情況有兩種。1.如果uncle節(jié)點(diǎn)不存在，那么cur一定是新插入節(jié)點(diǎn)。因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)，則cur和parent一定有一個(gè)黑色節(jié)點(diǎn)，就不滿(mǎn)足性質(zhì)4了，就像上圖中大家可以把叔叔節(jié)點(diǎn)刪掉，刪掉后發(fā)現(xiàn)cur一定是新增節(jié)點(diǎn)。

2.如果uncle節(jié)點(diǎn)存在，則其一定是黑色的。因?yàn)閏ur節(jié)點(diǎn)原先是黑色的，因?yàn)樾略龉?jié)點(diǎn)讓cur變成了紅色。如下圖：

?理解了以上知識(shí)我們?cè)倏纯吹谌N情況：

?三角形代表多種情況的子樹(shù)，我們可以看到如果cur和父節(jié)點(diǎn)和祖父節(jié)點(diǎn)不在一條直線(xiàn)上的時(shí)候，這個(gè)時(shí)候需要雙旋，（第一次旋轉(zhuǎn)的是parent，第二次旋轉(zhuǎn)的是grandfather,可以根據(jù)圖理解）雙旋后將cur變成黑色，把parent變成紅色，把grandfather變成紅色。代碼如下：

bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			//根節(jié)點(diǎn)必須為黑色
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		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 = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//開(kāi)始紅黑樹(shù)
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//向上調(diào)整
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//         g
					//      p     u
					//    c
					//如上圖，u為黑色或不存在，cur與grand和parent在一條直線(xiàn)，先單旋，再變色
					if (cur == parent->_left)
					{
						//右單旋的原因是單純左邊高，結(jié)合上圖
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//         g
					    //      p     u
					    //         c
						//當(dāng)cur在parent的右邊祖父節(jié)點(diǎn)和父節(jié)點(diǎn)和cur是折線(xiàn)形狀時(shí)，就是雙旋
						//由于父節(jié)點(diǎn)單純右邊高所以先左旋，然后整體高再右旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						parent->_col = RED;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				//parent是grandfather->right
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//向上調(diào)整
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//         g
					//      u     p
					//               c
					//如上圖，u為黑色或不存在，cur與grand和parent在一條直線(xiàn)，先單旋，再變色
					if (cur == parent->_right)
					{
						//左單旋的原因是單純左邊高，結(jié)合上圖
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//         g
						//      u     p
						//         c
						//當(dāng)cur在parent的右邊祖父節(jié)點(diǎn)和父節(jié)點(diǎn)和cur是折線(xiàn)形狀時(shí)，就是雙旋
						//由于父節(jié)點(diǎn)單純左邊高所以先右旋，然后整體高再左旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						parent->_col = RED;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

需要我們注意的是，第一種情況叔叔存在并且為紅色，這種情況需要向上調(diào)整所以不能break退出循環(huán)，但是第二種情況和第二種情況一旦旋轉(zhuǎn)后那么一定是平衡了所以直接break即可，在退出前我們將根節(jié)點(diǎn)顏色再次置為黑色，然后返回true即可。下面我們寫(xiě)一個(gè)析構(gòu)函數(shù)然后測(cè)試代碼：

~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

?注意了，上面我們沒(méi)有將單旋的代碼演示出來(lái)是因?yàn)閱涡虯VL中的實(shí)現(xiàn)一模一樣只不過(guò)沒(méi)有了平衡因子的修改。

下面我們想想如何判斷一顆樹(shù)是不是紅黑樹(shù)呢？要判斷紅黑樹(shù)只需要根據(jù)紅黑樹(shù)的幾條性質(zhì)就能判斷，代碼如下：

bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (_root&&_root->_col != BLACK)
		{
			cout << "根節(jié)點(diǎn)的顏色不是黑色" << endl;
			return false;
		}
		int benchMark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++benchMark;
			}
			cur = cur->_left;
		}
		return _Check(root, 0, benchMark);
	}
	bool _Check(Node* root, int blackNum, int benchMark)
	{
		if (root == nullptr)
		{
			if (blackNum != benchMark)
			{
				cout << "某條路徑的黑色節(jié)點(diǎn)與其他路徑不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}
		if (root->_col == RED 
			&& root->_parent 
			&& root->_parent->_col == RED)
		{
			cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
			return false;
		}
		return _Check(root->_left,blackNum,benchMark) && _Check(root->_right,blackNum,benchMark);
}

首先我們檢查根節(jié)點(diǎn)是否存在并且根節(jié)點(diǎn)是否是黑色，然后檢查每條節(jié)點(diǎn)的路徑是否相等以及是否有連續(xù)紅色節(jié)點(diǎn)，由于涉及到遞歸所以我們重新用另一個(gè)函數(shù)實(shí)現(xiàn)，在check函數(shù)中，我們的第二個(gè)參數(shù)是黑色節(jié)點(diǎn)數(shù)量，第三個(gè)參數(shù)是一個(gè)基準(zhǔn)值，這個(gè)基準(zhǔn)值我們給的是紅黑樹(shù)中最左路徑。當(dāng)遞歸到空樹(shù)有兩種情況，第一種情況是判斷當(dāng)前這條路徑的黑色節(jié)點(diǎn)數(shù)量是否與基準(zhǔn)值相同，如果不相同就返回false，相同就證明這條路徑遍歷完了返回true即可。每次遞歸遇到黑色節(jié)點(diǎn)就讓NUM++，這里是傳值傳參所以每條路徑的黑色節(jié)點(diǎn)數(shù)量互不影響。然后判斷當(dāng)前節(jié)點(diǎn)和其父節(jié)點(diǎn)是否都為紅色，這里判斷父親的原因是因?yàn)楹?jiǎn)單，如果判斷當(dāng)前節(jié)點(diǎn)和孩子節(jié)點(diǎn)是否有連續(xù)紅色節(jié)點(diǎn)的話(huà)，那么還要分左孩子和右孩子還要空的情況會(huì)更復(fù)雜。判斷父節(jié)點(diǎn)之前也先確定父節(jié)點(diǎn)是否存在，因?yàn)槿绻歉?jié)點(diǎn)的話(huà)父親為空。然后遞歸判斷每一顆子樹(shù)即可，下面我們就驗(yàn)證一下：

void test1()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	RBTree<int, int> at;
	for (auto& e : a)
	{
		at.insert(make_pair(e, e));
	}
	at.Inorder();
	cout << endl;
	cout << at.IsBalance() << endl;
}

void test2()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> rt;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand() + i;
		rt.insert(make_pair(x, x));
	}
	cout << rt.IsBalance() << endl;
}

?通過(guò)多次測(cè)試我們發(fā)現(xiàn)代碼并沒(méi)有問(wèn)題，以上就是紅黑樹(shù)的全部?jī)?nèi)容了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-451881.html

總結(jié)

到了這里，關(guān)于【C++】如何克服紅黑樹(shù)的恐懼？看這篇文章足夠了的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！