欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2024年08月11日 09:50:29   作者:大耳朵土土垚  
紅黑樹與AVL樹一樣,也是一種自平衡的二叉搜索樹,它在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色,可以是Red或Black,通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制,本文介紹了C++紅黑樹的底層實現(xiàn)機(jī)制,需要的朋友可以參考下

前言

紅黑樹與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)楹谏琯randparent節(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)楹谏?,grandparent節(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é)果如下:

5.結(jié)語

因為紅黑樹也是二叉搜索樹,其他的類似查找節(jié)點,析構(gòu)函數(shù)和構(gòu)造函數(shù)都與二叉搜索樹類似,對于刪除節(jié)點,可按照二叉搜索樹的方式將節(jié)點刪除,然后再進(jìn)行調(diào)整,大家有興趣可以自己查找了解一下

以上就是C++紅黑樹的底層實現(xiàn)機(jī)制詳解的詳細(xì)內(nèi)容,更多關(guān)于C++紅黑樹底層實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語言數(shù)據(jù)的存儲超詳細(xì)講解下篇浮點型在內(nèi)存中的存取

    C語言數(shù)據(jù)的存儲超詳細(xì)講解下篇浮點型在內(nèi)存中的存取

    使用編程語言進(jìn)行編程時,需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個變量時,就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息,操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型,來分配內(nèi)存和決定在保留內(nèi)存中存儲什么
    2022-04-04
  • C語言中設(shè)置進(jìn)程優(yōu)先順序的方法

    C語言中設(shè)置進(jìn)程優(yōu)先順序的方法

    這篇文章主要介紹了C語言中設(shè)置進(jìn)程優(yōu)先順序的方法,包括setpriority()函數(shù)和getpriority()函數(shù)以及nice()函數(shù),需要的朋友可以參考下
    2015-08-08
  • C++實現(xiàn)連連看消除算法

    C++實現(xiàn)連連看消除算法

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)連連看消除算法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-01-01
  • C語言異常處理機(jī)制案例講解

    C語言異常處理機(jī)制案例講解

    這篇文章主要介紹了C語言異常處理機(jī)制案例講解,本文講解了異常處理機(jī)制所用的函數(shù)和具體的代碼實現(xiàn)等,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++11模板元編程-std::enable_if示例詳解

    C++11模板元編程-std::enable_if示例詳解

    這篇文章主要給大家介紹了關(guān)于C++11模板元編程-std::enable_if的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-10-10
  • C++使用文件實現(xiàn)學(xué)生信息管理系統(tǒng)

    C++使用文件實現(xiàn)學(xué)生信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++使用文件實現(xiàn)學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-01-01
  • C語言實現(xiàn)簡單學(xué)生信息管理系統(tǒng)

    C語言實現(xiàn)簡單學(xué)生信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)簡單學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-07-07
  • 深入解析C++中的虛函數(shù)與多態(tài)

    深入解析C++中的虛函數(shù)與多態(tài)

    對C++ 了解的人都應(yīng)該知道虛函數(shù)(Virtual Function)是通過一張?zhí)摵瘮?shù)表(Virtual Table)和一個指向虛函數(shù)表的指針(vptr)來實現(xiàn)的
    2013-09-09
  • C++算法系列之中國農(nóng)歷的算法

    C++算法系列之中國農(nóng)歷的算法

    這篇文章主要介紹了C++計算中國農(nóng)歷的深入淺析,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧 
    2018-05-05
  • 使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu)

    使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu)

    這篇文章主要介紹了使用C語言使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu),包括根據(jù)前序序列和中序序列構(gòu)建二叉樹的方法,需要的朋友可以參考下
    2015-08-08

最新評論