C++紅黑樹的底層實現(xiàn)機制詳解

更新時間：2024年08月11日 09:50:29 作者：大耳朵土土垚

紅黑樹與AVL樹一樣,也是一種自平衡的二叉搜索樹,它在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色,可以是Red或Black,通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制,本文介紹了C++紅黑樹的底層實現(xiàn)機制,需要的朋友可以參考下

前言

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

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

紅黑樹的性質(zhì)：

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

所以紅黑樹的節(jié)點必須包含一個值類存儲該節(jié)點的顏色，我們可以利用枚舉來實現(xiàn)：

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

//節(jié)點類
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;	//存放數(shù)據(jù)
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;	//保存顏色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_col(RED)
	{}
};

//紅黑樹類
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false
	bool Insert(const pair<K, V>& data);
		
	// 檢測紅黑樹是否為有效的紅黑樹
	bool IsValidRBTRee();

	//中序遍歷
	void InOrder()
	{
		_InOrder(_pHead);
	}

private:
	void _InOrder(Node* root);
	
	bool Check(Node* root, int blackNum, const int refNum);
	
	// 左單旋
	void RotateL(Node* parent);
	// 右單旋
	void RotateR(Node* parent);
	
private:
	Node* _pHead = nullptr;
};

2.紅黑樹的插入

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

按照二叉搜索的樹規(guī)則插入新節(jié)點
檢測新節(jié)點插入后，紅黑樹的性質(zhì)是否造到破壞，如果破壞進(jìn)行相應(yīng)的修改操作

在插入新節(jié)點時，我們先確定一下新節(jié)點的顏色，如果是黑色，那么在插入后該條子路徑上就會多一個黑色節(jié)點，根據(jù)紅黑樹的性質(zhì)需要在其他路徑上都增加一個新節(jié)點才可以，比較麻煩，所以我們將新節(jié)點的顏色設(shè)為紅色，這樣如果其父親是黑色就剛剛好插入成功，如果父親是紅色我們就再來修改；所以我們將新節(jié)點的顏色設(shè)置為紅色：

//節(jié)點類
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;	//存放數(shù)據(jù)
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;	//保存顏色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_col(RED)		//直接在構(gòu)造時設(shè)置即可
	{}
};

先正常插入節(jié)點：

//1.先找到插入位置
//如果是空樹
if (_pHead == nullptr)
{
	Node* newnode = new Node(data);
	newnode->_col = BLACK;
	_pHead = newnode;
	return true;
}
//如果不是空樹
Node* cur = _pHead;
Node* parent = nullptr;
while (cur)
{
	if (cur->_kv.first > data.first)
	{
		parent = cur;
		cur = cur->_left;
	}
	else if (cur->_kv.first < data.first)
	{
		parent = cur;
		cur = cur->_right;
	}
	else
		return false;//沒找到返回false
}

//2.找到，插入節(jié)點
Node* newnode = new Node(data);
//判斷插入父節(jié)點左側(cè)還是右側(cè)
if (parent->_kv.first > data.first)
	parent->_left = newnode;
else
	parent->_right = newnode;

//更新newnode父節(jié)點
newnode->_parent = parent;

如果父節(jié)點是黑色，那么直接插入節(jié)點即可：

if (parent->_col == BLACK)
{
	//父節(jié)點是黑色,插入成功
	return true;
}

如果父節(jié)點是紅色，那么我們需要調(diào)整：

因為不可能有兩個紅色連在一起，所以我們需要進(jìn)行調(diào)整；而且父節(jié)點是紅色的話那么父節(jié)點肯定不是根節(jié)點且其父節(jié)點的顏色也只能是黑色，如下圖所示：

這時，我們就需要根據(jù)叔叔節(jié)點來進(jìn)行調(diào)整節(jié)點：

如果uncle節(jié)點是紅色：

我們就可以將unlcle和parent節(jié)點都變?yōu)楹谏?，grandparent節(jié)點變?yōu)榧t色：

這樣這兩條路徑的黑色節(jié)點依然是一個，沒有變，但是grandparent節(jié)點變?yōu)榧t色，如果它的父節(jié)點是黑色那么調(diào)整成功，但是如果其父節(jié)點是紅色，紅黑樹的性質(zhì)就不滿足，所以我們需要繼續(xù)向上調(diào)整。

如果uncle節(jié)點是黑色：

這時我們發(fā)現(xiàn)uncle節(jié)點的路徑上多了一個黑色節(jié)點，說明cur節(jié)點不可能是新增節(jié)點，這種情況是由上面uncle節(jié)點是紅色情況調(diào)整之后還需要繼續(xù)向上調(diào)整得來的(cur是上面情況的grandparent，grandparent的父節(jié)點也是紅色)，單純的變色已經(jīng)不能維持紅黑樹的性質(zhì)，我們需要進(jìn)行旋轉(zhuǎn)：

情況一：如果parent為grandparent的左孩子，cur為parent的左孩子，則進(jìn)行右單旋轉(zhuǎn)：

再將grandparent的顏色改為紅色，parent改為黑色。

情況二：如果parent為grandparent的右孩子，cur為parent的右孩子，則進(jìn)行左單旋轉(zhuǎn)：

再將grandparent的顏色改為紅色，parent改為黑色。

情況三：如果parent為grandparent的左孩子，cur為parent的右孩子，則先進(jìn)行左單旋轉(zhuǎn)換成情況一，再進(jìn)行右單旋：

再像情況一進(jìn)行右單旋：

再將grandparent的顏色改為紅色，cur改為黑色。

情況四：如果parent為grandparent的右孩子，cur為parent的左孩子，則先進(jìn)行右單旋轉(zhuǎn)換成情況二，再進(jìn)行左單旋：

再像情況二進(jìn)行左單旋：

再將grandparent的顏色改為紅色，cur改為黑色。

進(jìn)行旋轉(zhuǎn)后，紅黑樹就滿足了性質(zhì)，插入成功。

如果uncle不存在：

這種情況和uncle存在且為黑是一樣的，所以可以并入上面一起考慮。

完整代碼如下：

bool Insert(const pair<K, V>& data)
{
	//1.先找到插入位置
	//如果是空樹
	if (_pHead == nullptr)
	{
		Node* newnode = new Node(data);
		newnode->_col = BLACK;
		_pHead = newnode;
		return true;
	}
	//如果不是空樹
	Node* cur = _pHead;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first > data.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < data.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return false;//沒找到返回false
	}
	
	//2.找到，插入節(jié)點
	Node* newnode = new Node(data);
	//判斷插入父節(jié)點左側(cè)還是右側(cè)
	if (parent->_kv.first > data.first)
		parent->_left = newnode;
	else
		parent->_right = newnode;

	//更新newnode父節(jié)點和顏色
	newnode->_parent = parent;
	if (parent->_col == BLACK)
	{
		//父節(jié)點是黑色,插入成功
		return true;
	}
	if (parent->_col == RED)
	{
		//父節(jié)點是紅色
		cur = newnode;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;//parent是紅色，肯定不是根節(jié)點，所以grandparent不是空節(jié)點，而且是黑色
			
			//找叔叔節(jié)點
			Node* uncle = grandparent->_left;
			if (parent == grandparent->_left)
				uncle = grandparent->_right;
			
			if (uncle&&uncle->_col == RED)
			{
				//如果uncle是紅色
				//將unlcle和parent節(jié)點都變?yōu)楹谏琯randparent節(jié)點變?yōu)榧t色
				parent->_col = uncle->_col = BLACK;//即可保證所有路徑上黑色一樣多
				grandparent->_col = RED;
			
				//繼續(xù)往上更新
				cur = grandparent;
				parent = cur->_parent;
			}
			else if (uncle==nullptr||uncle->_col == BLACK)
			{
				//如果uncle不存在或者存在且為黑色
				if (grandparent->_left == parent && parent->_left == cur)
				{
					//右單旋,再將grandparent改為紅色，parent改為黑色
					RotateR(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else if (grandparent->_right == parent && parent->_right == cur)
				{
					//左單旋,再將grandparent改為紅色，parent改為黑色
					RotateL(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else if (grandparent->_right == parent && parent->_left == cur)
				{
					RotateR(parent);//先右單旋
					RotateL(grandparent);//再左單旋
					//再將grandparent的顏色改為紅色，cur改為黑色
					grandparent->_col = RED;
					cur->_col = BLACK;
				}
				else if (grandparent->_left == parent && parent->_right == cur)
				{
					RotateL(parent);//先左單旋
					RotateR(grandparent);//后右單旋
					//再將grandparent的顏色改為紅色，parent改為黑色
					grandparent->_col = RED;
					cur->_col = BLACK;
				}
				else
					assert(false);
				
				//插入成功，跳出循環(huán)
				break;
			}
		}

	}
	_pHead->_col = BLACK;//最后不管怎樣，根節(jié)點都是黑色
	return true;
}

因為涉及到多種情況，所以根節(jié)點的顏色可能會顧及不上，所以最后我們可以加一句_pHead->_col = BLACK;，這樣不管怎么樣，根節(jié)點都是黑色了。

左、右單旋函數(shù)與AVL樹的左、右單旋一樣：

// 左單旋
void RotateL(Node* parent)
{

	Node* cur = parent->_right;

	//將cur的左邊給parent的右邊，cur的左邊再指向parent
	parent->_right = cur->_left;
	cur->_left = parent;

	//鏈接cur與parent的父節(jié)點
	if (parent->_parent == nullptr)
	{
		//如果parent是根節(jié)點
		cur->_parent = nullptr;
		_pHead = cur;
	}
	else if (parent->_parent->_left == parent)
		parent->_parent->_left = cur;
	else
		parent->_parent->_right = cur;


	//更新父節(jié)點
	cur->_parent = parent->_parent;
	parent->_parent = cur;
	if (parent->_right)//判斷parent的右邊是否存在
		parent->_right->_parent = parent;

	
}
// 右單旋
void RotateR(Node* parent)
{
	Node* cur = parent->_left;

	//將cur的右邊給parent的左邊，cur的右邊再指向parent
	parent->_left = cur->_right;
	cur->_right = parent;

	//鏈接cur與parent的父節(jié)點
	if (parent->_parent == nullptr)
	{
		//如果parent是根節(jié)點
		cur->_parent = nullptr;
		_pHead = cur;
	}
	else if (parent->_parent->_left == parent)
		parent->_parent->_left = cur;
	else
		parent->_parent->_right = cur;


	//更新父節(jié)點
	cur->_parent = parent->_parent;
	parent->_parent = cur;
	if (parent->_left)
		parent->_left->_parent = parent;
}

紅黑樹的左、右單旋與AVL樹的區(qū)別在于不需要跟新平衡因子。

測試函數(shù)：

void RBTreeTest()
{
	RBTree<int, int> t;
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
}

3.紅黑樹的驗證

紅黑樹的驗證和AVL樹一樣，分為兩個步驟：

檢測其是否滿足二叉搜索樹(中序遍歷是否為有序序列)檢測其是否滿足紅黑樹的性質(zhì)

對于第二點：

// 檢測紅黑樹是否為有效的紅黑樹
bool IsValidRBTRee()
{
	if (_pHead == nullptr)
		return true;

	if (_pHead->_col == RED)
	{
		return false;
	}

	// 先求一條路徑上黑色節(jié)點數(shù)量作為參考值
	int refNum = 0;
	Node* cur = _pHead;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refNum;
		}

		cur = cur->_left;
	}

	return Check(_pHead, 0, refNum);
}

首先如果一棵樹是空樹滿足紅黑樹的性質(zhì)，返回true；其次如果根節(jié)點為紅色則不滿足紅黑樹的性質(zhì)，返回false；然后再根據(jù)每條路徑上是否有相同的黑色節(jié)點已及是否存在連續(xù)的紅色節(jié)點來進(jìn)一步判斷即Check()函數(shù)，但是我們需要先確定一條路上應(yīng)該有多少個黑色節(jié)點作為參考。

Check()函數(shù)如下：

bool Check(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		//cout << blackNum << endl;
		if (refNum != blackNum)
		{
			cout << "存在黑色節(jié)點的數(shù)量不相等的路徑" << endl;
			return false;
		}
		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在連續(xù)的紅色節(jié)點" << endl;
		return false;
	}

	if (root->_col == BLACK)
	{
		blackNum++;
	}

	return Check(root->_left, blackNum, refNum)
		&& Check(root->_right, blackNum, refNum);
}

因為Check()函數(shù)使用的是遞歸來計算每條路徑上黑色節(jié)點的數(shù)量，所以當(dāng)root為空時我們就可以將計算該條路徑上的黑色節(jié)點數(shù)量blackNum與參考值refNum進(jìn)行比較，如果相等返回true，不相等就返回fals；此外如果在計算黑色節(jié)點過程中存在連續(xù)的紅色節(jié)點也直接返回false即可。

測試函數(shù)：

void RBTreeTest()
{
	RBTree<int, int> t;
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
	
	cout << t.IsValidRBTRee() << endl;
}

4.中序遍歷

與二叉搜索樹一樣，可以使用遞歸進(jìn)行中序遍歷，并且遍歷結(jié)果是有序的，代碼如下：

//中序遍歷
void InOrder()
{
	_InOrder(_pHead);
}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

結(jié)果如下：