C++詳細(xì)實(shí)現(xiàn)紅黑樹流程詳解

更新時(shí)間：2022年06月10日 10:58:47 作者：愛生活，愛代碼

今天我要跟大家介紹二叉搜索樹中的另一顆樹——紅黑樹，它主要是通過控制顏色來控制自身的平衡，但它的平衡沒有AVL樹的平衡那么嚴(yán)格

紅黑樹的概念

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

概念總結(jié)：

紅黑樹是二叉搜索樹的升級，結(jié)點(diǎn)里面存放的成員col標(biāo)記當(dāng)前結(jié)點(diǎn)的顏色，它的最長路徑最多是最短路徑的二倍，紅黑樹通過各個(gè)結(jié)點(diǎn)著色方式的限制接近平衡二叉樹，但是不同于AVL的是AVL是一顆高度平衡的二叉樹，紅黑樹只是接近平衡

紅黑樹的性質(zhì)

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

紅黑樹性質(zhì)總結(jié)：

1、紅黑樹結(jié)點(diǎn)的顏色只能是紅色或者黑色

2、紅黑樹根節(jié)點(diǎn)必須是黑色

3、紅黑樹并沒有連續(xù)的紅色結(jié)點(diǎn)

4、紅黑樹中從根到葉子的每一條路徑都包含相同的黑色結(jié)點(diǎn)

5、葉子是黑色，表示空的位置

最長路徑和最短路徑概念：

最短路徑：從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)每一條路徑的結(jié)點(diǎn)顏色都是黑色的不包含紅色

最長路徑：紅黑交替，黑色結(jié)點(diǎn)和紅色結(jié)點(diǎn)的個(gè)數(shù)相等

思考：為什么滿足上面的性質(zhì)，紅黑樹就能保證：其最長路徑中節(jié)點(diǎn)個(gè)數(shù)不會超過最短路徑節(jié)點(diǎn)個(gè)數(shù)的兩倍？

假設(shè)結(jié)點(diǎn)個(gè)數(shù)為N，那么最短路徑就是logN，最長路徑就是2 * logN，所有并不存在最長路徑超過最短路徑2倍的情況

紅黑樹的定義與樹結(jié)構(gòu)

//枚舉紅黑顏色
enum colour 
{
	RED,
	BLACK,
};
//定義紅黑樹結(jié)點(diǎn)結(jié)構(gòu)
template<class K,class V>
struct RBTreeNode 
{
	//構(gòu)造
	RBTreeNode(const pair<K, V>& kv = {0,0})
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(BLACK)
	{ }
	//定義三叉鏈
	RBTreeNode<K, V>* _left; //左孩子
	RBTreeNode<K, V>* _right;//右孩子
	RBTreeNode<K, V>* _parent;  //父親
	pair<K, V> _kv;  //pair對象
	//節(jié)點(diǎn)的顏色
	colour _col;  //定義枚舉變量
};
//定義紅黑樹
template<class K, class V>
class RBTree 
{
		typedef RBTreeNode<K, V> Node;
	public:
		//構(gòu)造
		RBTree() 
			:_root(nullptr)
		{}
	private:
		Node* _root;  //定義樹的根節(jié)點(diǎn)
};

插入

插入過程類似搜索樹的插入，重要的是維護(hù)紅黑樹的性質(zhì)

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (!_root) //空樹處理
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return { _root, true };
	}
	//二叉搜索樹的插入邏輯
	Node* cur = _root, * parent = nullptr;
	while (cur)
	{
		if (cur->_kv.first < kv.first)//插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)大 
		{
			parent = cur;
			cur = cur->_right; 
		}
		else if (cur->_kv.first > kv.first) //插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)小 
		{
			parent = cur;
			cur = cur->_left; 
		}
		else 
		{
			return { cur, false }; //插入失敗
		}
	}
	cur = new Node(kv);
	cur->_col = RED;  //新增結(jié)點(diǎn)顏色默認(rèn)設(shè)置為RED
	//判斷插入結(jié)點(diǎn)是否在parent的左邊或者右邊
	if (parent->_kv.first > kv.first)  //左邊
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else     //右邊	
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	/* 紅黑樹性質(zhì)處理：
		如果這棵樹一開始是符合紅黑樹的性質(zhì)，但在新增結(jié)點(diǎn)之后，
		導(dǎo)致失去了紅黑樹的性質(zhì)，這里需要控制結(jié)點(diǎn)的顏色和限制
		每條路徑上黑色結(jié)點(diǎn)的個(gè)數(shù)，以上情況都要處理
    */
	while (parent && parent->_col == RED) //父親存在且父親為紅色
	{
		Node* grandfather = parent->_parent;  //祖父
		//父親出現(xiàn)在祖父的左邊需要考慮的情況
		if(parent == grandfather ->left)
		{
			//1、uncle存在，uncle為紅色
			/*
			   如果parent和uncle都存在并且都為紅色這是情況一，
			   需要將parent和uncle的顏色變成紅色，祖父顏色變成黑色
			   更新cur、parent、grandfather、uncle 繼續(xù)向上調(diào)整
			*/
			//2、uncle不存在
			/*  這里考慮兩種旋轉(zhuǎn)情況，直線單旋轉(zhuǎn)，折線雙旋
				/*
					cur出現(xiàn)在parent的左邊 ,右單旋轉(zhuǎn)
					經(jīng)過右單旋后，parent去做樹的根,祖父做為右子樹
					//調(diào)節(jié)結(jié)點(diǎn)顏色
					parent->_col = BLACK;
					grandfather->_col = RED;
				*/
				/*
					cur出現(xiàn)在parent的右邊，左右雙旋
					經(jīng)過雙旋后，cur作為樹的根，grandfather為右子樹
					調(diào)節(jié)結(jié)點(diǎn)顏色
					cur->_col = BLACK;
					grandfather->_col = RED;  
				*/
			*/ 
		}
		else  //父親出現(xiàn)在祖父的右邊
		{
			Node* uncle = grandfather->_left; //叔叔在左子樹 
			/*
			情況一：叔叔存在，且叔叔和父親都是紅色，那么就需要將父親
			和叔叔結(jié)點(diǎn)的顏色變成黑色，再將祖父的顏色變成紅色，
			繼續(xù)向上調(diào)整，更新孩子、父親、祖父、叔叔的位置
			*/
			/*
				情況二：叔叔不存在
				/*
				 	1、新增結(jié)點(diǎn)出現(xiàn)在父親的右邊，直線情況，左單旋處理
				 	旋轉(zhuǎn)完后parent去做父親的根，grandfather做父親
				 	的左子樹
							//調(diào)節(jié)顏色，根為黑，左右孩子為紅
					2、新增結(jié)點(diǎn)出現(xiàn)在父親的左邊，會出現(xiàn)折現(xiàn)的情況，
					引發(fā)雙旋，旋轉(zhuǎn)完后，cur變成根，
					parent和grandfaher去做cur的左右孩子
						   //調(diào)節(jié)顏色,根結(jié)點(diǎn)為黑，左右孩子為紅
				*/
			*/	
		}
	}
	//如果父親不存在為了保證根結(jié)點(diǎn)是黑色的，這里一定得將根結(jié)點(diǎn)處理為黑色
	_root->_col = BLACK;
}

新增結(jié)點(diǎn)插入后維護(hù)紅黑樹性質(zhì)的主邏輯

//1、父親一定存在的情況，叔叔存在/不存在 父親叔叔結(jié)點(diǎn)顏色為紅色
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
	Node* grandfather = parent->_parent;  //祖父
	//如果父親和叔叔結(jié)點(diǎn)顏色都是紅色
	if (parent == grandfather->_left)  
	{
		Node* uncle = grandfather->_right;  
		if (uncle && uncle->_col == RED)  //對應(yīng)情況：uncle存在且為紅
		{
			//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
			uncle->_col = parent->_col = BLACK; 
			grandfather->_col = RED;
			//向上調(diào)整
			cur = grandfather;  //調(diào)整孩子
			parent = cur->_parent;//調(diào)整父親
		}
		else   //uncle不存在，uncle存在且為黑
		{
			//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
			//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
			if (parent->_left == cur) 
			{
				RotateR(grandfather);
				parent->_col = BLACK;
				grandfather->_col = RED;
			}
			else  //parent->_right == cur 
			{	
				//折線情況(cur在parent的右邊)：這里會引發(fā)雙旋
				RotateL(parent);  //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
				RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
				//旋轉(zhuǎn)完后cur會去做樹的根，那么設(shè)置為黑色，
				//為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
				cur->_col = BLACK;
				grandfather->_col = RED;  //黑色	結(jié)點(diǎn)個(gè)數(shù)相同
			}
		}
	}
	else //父親在右子樹
	{
			Node* uncle = grandfather->_left; //叔叔在左子樹 
			if (uncle&& uncle->_col == RED)  //情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）
			{
				//根據(jù)情況一處理即可：叔叔和父親變黑，
				//祖父變紅(目的是為了每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同)，繼續(xù)向上
				cur = grandfather;  //孩子
				parent = cur->_parent;//父親
			}
			else //叔叔不存在 
			{
				if (cur == parent->_right)  //新增結(jié)點(diǎn)在父親的右邊，直線情況左單旋處理
				{
					//左單旋轉(zhuǎn)，以grandfather為旋轉(zhuǎn)點(diǎn)，旋轉(zhuǎn)完后parent去做新的根，grandfather去做左子樹
					RotateL(grandfather);
					//調(diào)節(jié)顏色
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else //新增結(jié)點(diǎn)在父親的左邊，折線情況，引發(fā)雙旋
				{
					//處理：以parenrt為旋轉(zhuǎn)點(diǎn)做右單旋，再以grandfather為旋轉(zhuǎn)點(diǎn)做左單旋
					RotateR(parent);  //右旋
					RotateL(grandfather); //左旋
					parent->_col = grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
		}
	_root->_col = BLACK;
}

拆解討論：

以下只列舉parent在grandfather左邊的情況，而parent在grandfather右邊的情況處理方式只是反過來的，讀者可以自行畫圖，這里僅留參考代碼

Node* uncle = grandfather->_right;  
if (uncle && uncle->_col == RED)  //對應(yīng)情況：uncle存在且為紅
{
	//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
	uncle->_col = parent->_col = BLACK; 
	grandfather->_col = RED;
	//向上調(diào)整
	cur = grandfather;  //調(diào)整孩子
	parent = cur->_parent;//調(diào)整父親
}

else   //uncle不存在，uncle存在且為黑
{
	//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
	//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
	if (parent->_left == cur) 
	{
		RotateR(grandfather);
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	else  //parent->_right == cur 
	{	
		//雙旋轉(zhuǎn)
	}
}

//折線情況(cur在parent的右邊)：這里會引發(fā)雙旋
RotateL(parent);  //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
//旋轉(zhuǎn)完后cur會去做樹的根，那么設(shè)置為黑色，
//為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
cur->_col = BLACK;
grandfather->_col = RED;

旋轉(zhuǎn)

void RotateR(Node* parent) //右單旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) subLR->_parent = parent;  //防止subLR為nullptr
		subL->_right = parent;
		Node* parent_parent = parent->_parent; //指針備份
		parent->_parent = subL;
		if (_root == parent) //如果parent就是樹的根 
		{
			_root = subL;  //subL取代parent
			_root->_parent = nullptr;
		}
		else  //如果parent并不是樹的根
		{
			if (parent_parent->_left == parent) parent->_left = subL;
			else parent_parent->_right = subL;
			subL->_parent = parent_parent; //subL去做parent_parent的孩子
		}
	}
	//左單旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		subR->_left = parent;
		Node* parent_parent = parent->_parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent_parent->_left == parent) parent_parent->_left = subR;
			else parent_parent->_right = subR;
			subR->_parent = parent_parent;
		}
	}

驗(yàn)證

/*
	紅黑樹的幾點(diǎn)性質(zhì)在于：
	1、根結(jié)點(diǎn)必須是紅色的
	2、不會出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
	3、所有路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count) 
{
	if (!root) 
	{
		if (isBlackNum != count) 
		{
			printf("黑色結(jié)點(diǎn)個(gè)數(shù)不均等\n");
			return false;
		}
		return true; //遍歷完整棵樹，如果以上列舉的非法情況都不存在就返回true
	}
	//檢查是否出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
	if (root->_col == RED && root->_parent->_col == RED) 
	{
		printf("出現(xiàn)了連續(xù)的紅色結(jié)點(diǎn)\n");
		return false;
	} 
	//走前序遍歷的過程中記錄每一條路徑黑色結(jié)點(diǎn)的個(gè)數(shù)
	if (root->_col == BLACK) count++;
	//遞歸左右子樹
	return _CheckBlance(root->_left, isBlackNum, count) && 
			_CheckBlance(root->_right, isBlackNum, count);
}
//驗(yàn)證紅黑樹
bool CheckBlance()
{
	if (!_root) return true;  //樹為null
	//根結(jié)點(diǎn)是黑色的
	if (_root->_col != BLACK) 
	{
		printf("根結(jié)點(diǎn)不是黑色的\n");
		return false;
	}
	//每一條路徑黑色結(jié)點(diǎn)的個(gè)數(shù)必須是相同的，
	int isBlcakNum = 0;
	Node* left = _root; 
	while (left) 
	{
		if (left->_col == BLACK) isBlcakNum++; // 統(tǒng)計(jì)某一條路徑的所以黑色結(jié)點(diǎn)個(gè)數(shù)
		left = left->_left;
	}
	//檢查連續(xù)的紅色結(jié)點(diǎn)，檢查每一條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是否相等
	return _CheckBlance(_root, isBlcakNum ,0);
}

紅黑樹與AVl樹的比較

紅黑樹與AVL樹的比較

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的

時(shí)間復(fù)雜度都是O( log n)，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡單，所以實(shí)際運(yùn)用中紅黑樹更多。