紅黑樹(RBTree)的簡單操作

紅黑樹介紹

紅黑樹，是一種二叉搜尋樹，但在每個結點上增加一個存儲位表示結點的顔色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點着色方式的限制，紅黑樹確定沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

性質

每個結點不是紅色就是黑色
根節點是黑色的
如果一個節點是紅色的，則它的兩個孩子結點是黑色的
對于每個結點，從該結點到其所有後代葉結點的簡單路徑上，均包含相同數目的黑色結點
每個葉子結點都是黑色的(此處的葉子結點指的是空結點）

如下圖為一顆紅黑樹

紅黑樹(RBTree)的簡單操作

比如17這個結點開始，它的左子樹以及右子樹中黑色結點的個數都是1個。**值得注意的是，葉子節點是黑色，上圖中的1,6,11,15,22,27結點中其實還是有兩個孩子，隻不過該孩子為NULL，**是以是這裡所說的值得是空結點。在紅黑樹中，也需要用到左旋或者右旋，将在下面介紹到。

注意

下列代碼中各類解釋都會在代碼中注釋

RBTree的結點定義

enum Color
{
	BLACK,//表示黑色結點
	RED//表示紅色結點
};
//模闆建立，K代表key值，V代表value值
tenmplate<class K,class V>
struct RBTreeNode
{
	pair<K,V> _value;//結點值
	Color _color;//結點顔色
	RBTreeNode<K,V>* _left;//左孩子指針
	RBTreeNode<K,V>* _right;//右孩子指針
	RBTreeNode<K,V>* _parent;//父指針
	RBTreeNode(const pair<K, V>& value = pair<K,V>())
		::_value(value)
		, _color(RED)//每個預設為紅色
		, _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

RBTree類

template<class K,class V>
class RBTree
{
public:
	typedef RBTreeNode<K,V> Node; 
	RBTree()//初始化
		:_header(new Node)
	{
		//剛開始左右指針都指向_header
		_header->_left = _header->_right = _header;
	}
	bool insert(const pair<K, V>& val);//紅黑樹的插入
	Node* leftMost()//尋找紅黑樹最左結點
	Node* rightMost()//尋找紅黑樹的最右結點
	void RotateR(Node* parent)//右旋
	void RotateL(Node* parent)//左旋
	void inorder()//紅黑樹的中序周遊，輸出有序
private:
	Node* _header;//指向根結點的指針
};

紅黑樹的調整及左旋和右旋

因為新節點的預設顔色是紅色，是以：如果其雙親節點的顔色是黑色，沒有違反紅黑樹任何性質，則不需要調整；但當新插入節點的雙親節點顔色為紅色時，就違反了性質三不能有連在一起的紅色節點，此時需要對紅黑樹分情況來讨論：

這裡做一個定義：

cur表示目前結點，p表示父結點，g為祖父結點,u為叔叔結點

情況1：

cur為紅色，p為紅色，u存在且為紅色，g為黑色

如下圖

紅黑樹(RBTree)的簡單操作

解決方法：

1.cur顔色不變，p,u結點變為黑色，g結點變為紅色。

2.将g賦給cur，向上繼續檢查各節點顔色是否合法

3.對于g結點，如果g為根結點，則在調整完成後，将其結點改為黑色即可，如果g是某個結點的子樹，則它比存在雙親，這時隻需要繼續向上檢查即可，即重複2步驟。

上圖改變後如下圖

1.g為根結點

紅黑樹(RBTree)的簡單操作

2.g不為根結點

紅黑樹(RBTree)的簡單操作

g的顔色變為紅色後，繼續看g的父結點m結點的顔色開始向上繼續檢查即可。

情況2：

cur為紅，p為紅，g為黑，u不存在/u為黑。p為g的左孩子且cur為p的左孩子或p為g的右孩子且cur為p的右孩子

注意：u存在的話則一定為黑色，因為要滿足性質4，如果u不存在，則cur插入的新節點的父結點必為紅色，g為黑色，則此時不滿足性質4，需要調整。

如下圖u存在

紅黑樹(RBTree)的簡單操作

解決步驟

1.p為g的左孩子，cur為p的左孩子，則進行右單旋轉；相反， p為g的右孩子，cur為p的右孩子，則進行左單旋轉 (上圖展示的是p為g的左孩子，cur為p的左孩子，則需要右旋）

2.p、g變色----->p變黑，g變紅

上圖調整後如下圖

紅黑樹(RBTree)的簡單操作

情況3：

cur為紅，p為紅，g為黑，u不存在/u為黑，p為g的左孩子且cur為p的右孩子或p為g的右孩子且cur為p的左孩子

如下圖情況

紅黑樹(RBTree)的簡單操作

解決步驟

1.若p為g的左孩子，cur為p的右孩子，則對p結點進行左旋，交換cur和p結點，此時變為情況2中的p為g的左孩子且為紅，cur為p的左孩子且為紅。

若p為g的右孩子，cur為p的左孩子，則對p結點進行右旋，交換cur和p結點，此時變為了情況2中的p為g的右孩子且為紅，cur為p的右孩子且為紅。

(上圖展示的是p為g的左孩子，cur為p的右孩子的情況)

2.針對旋轉後對應的情況2的某種情況繼續旋轉即可

右旋

void RotateR(Node* parent)
{
	Node* subl = parent->_left;//取parent的左孩子subl
	Node* sublr = subl->_right;//取subl的右孩子
	parent->_left = sublr;//parent的左孩子變為sublr
	subl->_right = parent;//subl的右孩子變為parent
	//如果sublr存在不為空，則更新sublr的父親
	if(sublr) sublr->_parent = parent;
	//如果parent為根結點
	if(_header->_parent == parent) 
	{
		_header->_parent = subl;//subl更新為根結點
		subl->_parent = _header;//s更新ubl的父結點為_header
	}
	//如果parent不為根結點
	else
	{
		Node* p = parent->_parent;//擷取parent的父親結點
		subl->_parent = p;//subl的父親結點更新為p
		//如果p的左孩子為parent，則更新p的左孩子為subl
		if(p->_left == parent)	p->_left = subl;
		else  p->_right = subl;//否則p的右孩子為subl
	}
	parent->_parent = subl;//最後更新parent的父結點
}

左旋

void RotateL(Node* parent)
{
	Node* subr = parent->_right;//擷取parent的右孩子subr
	Node* subrl = subr->_left;//擷取subr的左孩子subrl
	subr->_left = parent;//更新subr的左孩子為parent
	parent->_right = subrl;//更新parent的右孩子為subrl
	//如果subrl存在則subrl的父親為parent
	if(subrl)  subrl->_parent = parent;
	//如果parent為根結點
	if(_header->_parent == parent)
	{
		_header->_parent = subr;//更新新的根結點
		subr->_parent = _header;//subr的父親指向_header
	}
	//如果不為根結點
	else
	{
		Node* p = parent->_parent;//擷取parent的父親結點p
		subr->_parent = p;//更新subr的父結點為p
		//如果p的左孩子為parent更新p的左孩子為subr
		if(p->_left == parent)	p->_left = subr;
		//否則更新p的右孩子為subr
		else  p->_right = subr;
	}
	//最後更新parent的父親
	parent->_parent = subr;
}

RBTree的插入

這裡和之前說的AVL樹的插入一樣，隻不過調整不一樣。

bool insert(const pair<K, V>& val)
{
	//如果插入的為根結點
	if(_header->_parent == nullptr)
	{
		Node* root = new Node(val);
		root->_color = BLACK;//根結點置為黑色
		_header->_parent = root;//_header的父親為root
		root->_parent = _header;//root的父親為_header
		//_header的左右指針分别指向root
		_header->_left = root;
		_header->_right = root;
		return true;//擦汗如成功傳回true
	}
	else//插入的不為根結點
	{
		Node* cur = _header->_parent;//擷取根結點友善周遊
		Node* parent = nullptr;//parent表示cur的父親
		//cur不為空
		while(cur)
		{
			parent = cur;//parent為cur的父親結點
			//如果key值相同，則傳回false
			if(cur->_value.first == val.first) return false;
			//如果需要插入的結點key值小于目前結點key值，則繼續向cur的左孩子周遊
			if(cur->_value.first > val.first) cur = cur->_left;
			//否則向cur的右孩子周遊
			else cur = cur->_right;
		}
		//當跳出上述循環後，表示找到一個為空的地方插入val
		cur = new Node(val);
		//判斷cur為parent的左孩子還是右孩子
		if(parent->_value.first<val.first)	parent->_right = cur;
		else  parent->_left = cur;
		cur->_parent = parent;//更新cur的父親
		//調整判斷
		//表示cur不為根結點，且有兩個連續的紅色結點
		while(cur != _header->_parent && cur->_parent->_color == RED)
		{
			Node* p = cur->_parent;//擷取cur的父親結點
			Node* g = p->_parent;//擷取cur的祖父結點
			//如果p為g的左孩子
			if(g->_left == p)
			{
				Node* u = g->_right//擷取cur的叔叔結點
				if(u&&u->_color == RED)//如果u存在且u的顔色為RED
				{
				//跟新p,u的顔色為BLACK
					p->_color = u->_color = BLACK;
					g->_color = RED;//更新g的顔色為RED
					cur = g;//繼續向上更新檢查
				}
				else//表示u不存在或者u的顔色為BLACK
				{
					//這裡可以先判斷是否存在情況3，如果存在則變為情況2後繼續旋轉，否則直接按照情況2的對應情況進行旋轉即可
					if(cur == p->_right)
					{
						RotateL(p);//以p進行左旋
						swap(cur, p);//交換cur和p結點
					}
					//不論上述是否旋轉，都表示此時為情況2
					RotateR(g);//以g結點進行右旋
					//修改顔色
					p->_color = BLACK;
					g->_color = RED;
					break;
				}
			}
			else//否則p為g的右孩子
			{
				Node* u = g->_left;//擷取cur的叔叔結點u
				if(u&&u->_color == RED)
				{
				//更新顔色
					p->_color = u->_color = BLACK;
					g->_color = RED;
					cur = g;//繼續向上更新
				}
				else//表示u不存在或者u的顔色為黑色
				{
					if(p->_left == cur)
					{
						RotateR(p);//以p進行右旋
						swap(cur, p);//交換cur和p結點
					}
					//此時為情況2
					RotateL(g);
					//修改顔色
					p->_color = BLACK;
					g->_color = RED;
					break;
				}
			}
		}
	}
	//根顔色置為黑色
	_header->_parent->_color = BLACK;
	//更新_header的左，右
	_header->_left = leftMost();
	_header->_right = rightMost();
	return true;
}

擷取RBTree的最左和最右結點

該函數會在自我實作紅黑樹的疊代器時用的，因為紅黑樹的周遊為中序，疊代器則需要該樹的最左和最右結點，将來最右結點相當于begin()位置，最右結點相當于end()。

Node* leftMost()//尋找紅黑樹最左結點
{
	Node* cur = _header->_parent;
	while(cur&&cur->_left)
		cur = cur->_left;
	return cur;
}
Node* rightMost()//尋找紅黑樹的最右結點
{
	Node* cur = _header->_right;
	while(cur&&cur->_right)\
		cur = cur->_right;
	return cur;
}

RBTree的周遊

這裡就是中序周遊即可，但是注意一下需要封裝一下周遊

void inoder()
{
	Node* root = _header->_parent;
	_inoder(root);
}
void _inoder(Node* root)
{
	if(root)
	{
		_inoder(root->_left);
		cout<<root->_value.first<<" "<<root->_value.second<<endl;
		_inoder(root->_right);
	}
}

以上就是紅黑樹的簡單操作

紅黑樹(RBTree)的簡單操作

紅黑樹介紹

RBTree的結點定義

RBTree類

紅黑樹的調整及左旋和右旋

RBTree的插入

擷取RBTree的最左和最右結點

RBTree的周遊

繼續閱讀

2021-08-13c++——類之操作符重載

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器