#include <iostream>

using namespace std;

enum Color{
	RED,
	BLACK,
};

template <class K,class V>
struct RBTreeNode
{
	K _key;
	V _value;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Color _color;

	RBTreeNode(const K& key, const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _color(RED)
	{}
};

template <class K,class V>

class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;

	RBTree()
		:_root(NULL)
	{}

	bool Insert(const K& key, const V& value)
	{
		if (_root == NULL)
		{
			_root = new Node(key,value);
			_root->_color = BLACK;
			return true;
		}

		Node* cur = _root, *prev = NULL;

		while (cur)
		{
			if (cur->_key < key)
			{
				prev = cur;
				if (cur->_right){
					cur = cur->_right;
				}
				else
				{
					cur->_right = new Node(key, value);
					cur = cur->_right;
					cur->_parent = prev;
					break;
				}
			}
			else if (cur->_key>key)
			{
				prev = cur;
				if (cur->_left){
					cur = cur->_left;
				}
				else
				{
					cur->_left = new Node(key, value);
					cur = cur->_left;
					cur->_parent = prev;
					break;
				}
			}
			else
				return false;
		}
		Node* gf = prev->_parent;

		while (gf)
		{
			if (prev->_color == BLACK)
				break;
			Node* uc = NULL;
			if (prev == gf->_left)
				uc = gf->_right;
			else
				uc = gf->_left;
			if (uc == NULL||uc->_color==BLACK)
			{
				//單旋
				if (prev == gf->_left&&cur == prev->_left){//右旋
					RotateR(prev, gf);
					prev->_color = BLACK;
					gf->_color = RED;
				}
				else if (prev == gf->_right&&cur == prev->_right){//左旋
					RotateL(prev, gf);
					prev->_color = BLACK;
					gf->_color = RED;
				}
				//雙旋
				else if (prev == gf->_right&&cur == prev->_left)//右左旋
				{
					RotateR(cur,prev);
					RotateL(prev,gf);
					prev->_color = BLACK;
					gf->_color = RED;
				}
				else//左右旋
				{
					RotateL(cur, prev);
					RotateR(prev, gf);
					prev->_color = BLACK;
					gf->_color = RED;
				}
			}
			else
			{
				prev->_color = BLACK;
				uc->_color = BLACK;
				if (gf == _root)
					return true;
				gf->_color = RED;
				cur = gf;
				prev = cur->_parent;
				gf = prev->_parent;
			}
		}
		return true;

	}

	void RotateR(Node* subL,Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* subLR = subL->_right;

		subL->_right = parent;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		if (ppNode){
			subL->_parent = ppNode;
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
		}
		else
			_root = subL;

	}
	void RotateL(Node* subR, Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* subRL = subR->_left;

		subR->_left = parent;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		if (ppNode){
			subR->_parent = ppNode;
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
		}
		else
			_root = subR;
	}

	bool Remove(const K& key)
	{
	}

	bool IsBalance()//是否平衡
	{
		if (_root == NULL)
			return true;
		int num = 0;
		Node* tmp = _root;
		while (tmp)
		{
			if (tmp->_color == BLACK)
				num++;
			tmp = tmp->_left;
		}
		return _IsBalance(_root,num);
	}

	

private:
	Node* _root;
	bool _IsBalance(Node* root, int num)
	{
		if (root == NULL)
			return true;
		if (root->_color == BLACK)
			num--;
		if (root->_color == RED){
			if (root->_left&&root->_left->_color == RED || root->_right&&root->_right->_color == RED)
			{
				cout << "color not balance! key:" << root->_key << endl;
				return false;
			}
		}
		if (root->_left == NULL&&root->_right == NULL)
		{
			if (num == 0)
				return true;
			else
			{
				cout << "num not balance! key:" << root->_key << endl;
				return false;
			}
		}

		return _IsBalance(root->_left, num) && _IsBalance(root->_right, num);
	}
};

創(chuàng)新互聯(lián)建站致力于互聯(lián)網(wǎng)網(wǎng)站建設(shè)與網(wǎng)站營銷，提供成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、網(wǎng)站開發(fā)、seo優(yōu)化、網(wǎng)站排名、互聯(lián)網(wǎng)營銷、小程序開發(fā)、公眾號商城、等建站開發(fā)，創(chuàng)新互聯(lián)建站網(wǎng)站建設(shè)策劃專家，為不同類型的客戶提供良好的互聯(lián)網(wǎng)應(yīng)用定制解決方案，幫助客戶在新的全球化互聯(lián)網(wǎng)環(huán)境中保持優(yōu)勢。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁標(biāo)題：c++紅黑樹的插入-創(chuàng)新互聯(lián)
URL鏈接：http://jinyejixie.com/article4/iseie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站營銷、虛擬主機(jī)、網(wǎng)站導(dǎo)航、品牌網(wǎng)站制作、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)