一、紅黑樹

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)華陰,十年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108

1、定義：紅黑樹是一棵二叉搜索樹，它在每個(gè)節(jié)點(diǎn)上增加了一個(gè)存儲(chǔ)位來表示節(jié)點(diǎn)的顏色，可以是Red或Black。通過對任何一條從根到葉子簡單路徑上的顏色來約束，紅黑樹保證最長路徑不超過最短路徑的兩倍，因而近似于平衡。

2、性質(zhì)：

• 每個(gè)節(jié)點(diǎn)，非黑即紅；

• 根節(jié)點(diǎn)為黑色；

• 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的2個(gè)子節(jié)點(diǎn)是黑色的(沒有連續(xù)的紅節(jié)點(diǎn))；

• 對每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。（每條路徑的黑色節(jié)點(diǎn)的數(shù)量相等）；

• 每個(gè)葉子節(jié)點(diǎn)都是黑色的（這里的葉子節(jié)點(diǎn)是指的NIL節(jié)點(diǎn)（空節(jié)點(diǎn)））；

二、紅黑樹相關(guān)

1、紅黑樹保證最長路徑不超過最短路徑的兩倍，因而近似于平衡。

    如圖所示，插入節(jié)點(diǎn)后，為了保持紅黑樹，最長路徑最多是最短路徑的 2倍。

2、插入節(jié)點(diǎn)：

 注：cur為當(dāng)前節(jié)點(diǎn)，parent父節(jié)點(diǎn)，grandpa祖父節(jié)點(diǎn)，uncle叔叔節(jié)點(diǎn)

（1）第一種情況

cur為紅，parent為紅，grandpa為黑，uncle存在且為紅 --->

則將parent,uncle改為黑，grandpa改為紅，然后把grandpa當(dāng)成cur，繼續(xù)向上調(diào)整。

（2）第二種情況

cur為紅，parent為紅，grandpa為黑，uncle不存在/uncle為黑 ---> 

parent為grandpa的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；相反，p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn);

parent、grandpa變色--parent變黑，grandpa變紅。

（3）第三種情況

cur為紅，parent為紅，grandpa為黑，uncle不存在/uncle為黑 --> 

parent為grandpa的左孩子，cur為parent的右孩子，則針對parent做左單旋轉(zhuǎn)；相反，parent為grandpa的右孩子，cur為p的左孩子，則針對parent做右單旋轉(zhuǎn),則轉(zhuǎn)換成了情況2。

3、判斷紅黑樹：根據(jù)紅黑樹的性質(zhì)進(jìn)行判定。

4、紅黑樹和AVL樹的比較：

    紅黑樹和AVL樹都是高效的平衡二叉樹，增刪查改的時(shí)間復(fù)雜度都是O(lg(N))；

    紅黑樹的不追求完全平衡，保證最長路徑不超過最短路徑的2倍，相對而言，降低了旋轉(zhuǎn)的要求，所以性能跟AVL樹差不多，但是紅黑樹實(shí)現(xiàn)更簡單，所以實(shí)際運(yùn)用中紅黑樹更多。

三、相關(guān)實(shí)現(xiàn)

1、節(jié)點(diǎn)

enum Color
{
	RED,BLACK,
};
template
struct RBTreeNode
{
	RBTreeNode *_left;
	RBTreeNode *_right;
	RBTreeNode *_parent;
	K _key;
	V _value;
	Color _col;
	RBTreeNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_col(RED)
		,_left(NULL)
		,_right(NULL)
		,_parent(NULL)
	{}
};

2、紅黑樹及相關(guān)實(shí)現(xiàn)

template
class RBTree
{
	typedef RBTreeNode Node;
public:
	RBTree()
		:_root(NULL)
	{}
	
	bool Insert(const K& key,const V& value)
	{
		//插入節(jié)點(diǎn)
		if(_root == NULL)
		{
			_root=new Node(key,value);
			return true;
		}
		Node *cur=_root;
		Node *parent=NULL;
		while(cur)
		{
			if(cur->_key < key)
			{
				parent=cur;
				cur=cur->_right;
			}
			else if(cur->_key > key)
			{
				parent=cur;
				cur=cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur=new Node(key,value);
		if(parent->_key < key)
		{
			parent->_right=new Node(key,value);
			parent->_right=parent;
		}
		else
		{
			parent->_left=new Node(key,value);
			parent->_right=parent;
		}
		//更正信息
		while(cur != _root && parent->_col == RED)
		{
			Node *grandpa=parent->_right;
			if(grandpa->_left == parent)
			{
				Node *uncle=grandpa->_right;
				if(uncle && uncle->_col == RED) // 第1種情況
				{
					parent->_col=uncle->_col=BLACK;
					grandpa->_col=RED;
					//繼續(xù)向上調(diào)
					cur=grandpa;
					parent=cur->_parent;
				}
				else
				{
					// 第3種情況：雙旋轉(zhuǎn) --> 單旋轉(zhuǎn)
					if(cur == parent->_right)
					{
						RotateL(parent);//左單旋
						swap(cur,parent);
					}
					//第2種情況
					parent->_col=BLACK;
					grandpa->_col=RED;
					RotateR(grandpa);//右單旋
					break;
				}
			}
			else
			{
				Node *uncle=grandpa->_left;
				if(uncle && uncle->_col == RED) // 第1種情況
				{
					parent->_col=uncle->_col=BLACK;
					grandpa->_col=RED;
					//繼續(xù)向上調(diào)
					cur=grandpa;
					parent=cur->_parent;
				}
				else  
				{
					// 第3種情況：雙旋轉(zhuǎn) --> 單旋轉(zhuǎn)
					if(cur == parent->_left)
					{
						RotateR(parent);//左單旋
						swap(cur,parent);
					}
					//第2種情況
					parent->_col=BLACK;
					grandpa->_col=RED;
					RotateR(grandpa);//右單旋
					break;
				}
			}
		}
		return true;
	}

	bool IsBlance()
	{
		if(_root == NULL) return;
		if(_root->_col == RED) return false;
		int k=0;
		Node *cur=_root;
		while(cur)
		{
			if(cur->_col == BLACK)
				++k;
			cur=cur->_left;
		}
		int count=0;
		return _IsBlance(_root,k,count);
	}

protected:
	bool _IsBlance(Node *root,const int k,int count)
	{
		if(root == NULL) return true;
		//紅黑樹父子節(jié)點(diǎn)顏色不能相同
		if(root->_col == RED && root->_parent->_col == RED)
		{
			cout<<"錯(cuò)誤：出現(xiàn)連續(xù)紅色節(jié)點(diǎn)"_key<_col == BLACK)
			++count;
		//每條路徑中黑色節(jié)點(diǎn)數(shù)量相等
		if(root->_left == NULL && root->_right == NULL && k != count)
		{
			cout<<"錯(cuò)誤：黑色節(jié)點(diǎn)數(shù)目不等"<_left,k,count) && _IsBlance(root->_right,k,count);
	}

protected:
	Node *_root;
};

3、總結(jié)：

    紅黑樹也是一種平衡二叉樹，通過存儲(chǔ)節(jié)點(diǎn)的顏色紅黑，對其進(jìn)行處理，使其處于平衡狀態(tài)。紅黑樹插入節(jié)點(diǎn)時(shí)，主要分三種情況，按照不同情況處理。刪除時(shí)和AVL樹類似，只是需要注意旋轉(zhuǎn)及更該節(jié)點(diǎn)顏色。