紅黑樹是滿足下面性質(zhì)的二叉搜索樹

專業(yè)從事網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作,高端網(wǎng)站制作設(shè)計(jì),小程序開發(fā),網(wǎng)站推廣的成都做網(wǎng)站的公司。優(yōu)秀技術(shù)團(tuán)隊(duì)竭力真誠(chéng)服務(wù)，采用H5響應(yīng)式網(wǎng)站+CSS3前端渲染技術(shù)，成都響應(yīng)式網(wǎng)站建設(shè)公司，讓網(wǎng)站在手機(jī)、平板、PC、微信下都能呈現(xiàn)。建站過程建立專項(xiàng)小組，與您實(shí)時(shí)在線互動(dòng)，隨時(shí)提供解決方案，暢聊想法和感受。

1. 每個(gè)節(jié)點(diǎn)，不是紅色就是黑色的

2. 根節(jié)點(diǎn)是黑色的

3. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)是黑色的

4. 對(duì)每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。

#pragma once

enum Color{ RED, BLACK };

template
struct RBtreeNode
{
	RBtreeNode(const K& key, const V& v, Color col = RED)
	:_left(NULL)
	, _right(NULL)
	, _parent(NULL)
	, _key(key)
	, _vlaue(v)
	, _col(col)
	{}
	RBtreeNode* _left;
	RBtreeNode* _right;
	RBtreeNode* _parent;
	K _key;
	V _vlaue;
	Color _col;
};
template
class RBtree
{
	typedef RBtreeNode Node;
public:
	RBtree()
		:_root(NULL)
	{}
	bool Insert(const K& key, const V& v)
	{
		if (_root == NULL)
		{
			_root = new Node(key, v, BLACK);
			return true;
		}
		Node* parent = NULL;
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key, v, RED);
		if (key < parent->_key)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//調(diào)色
		while (cur != _root && parent->_col == RED)
		{
			Node* GrandParent = parent->_parent;
			if (parent == GrandParent->_left)//往左子樹插
			{
				Node* uncle = GrandParent->_right;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					GrandParent->_col = RED;

					cur = GrandParent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						_RotateL(parent);
						swap(cur, parent);
					}
					_RotateR(GrandParent);
					parent->_col = BLACK;
					GrandParent->_col = RED;
				}
			}
			else//往右子樹插
			{
				Node*uncle = GrandParent->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					GrandParent->_col = RED;

					cur = GrandParent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						_RotateR(parent);
						swap(cur, parent);
					}
					_RotateL(GrandParent);

					parent->_col = BLACK;
					GrandParent->_col = RED;
				}

			}
		}
		_root->_col = BLACK;
		return true;
	}
	bool IsBalanceTree()
	{
		return _IsBalance(_root);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
protected:
	int _Height(Node* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		int left = _Height(root->_left) + 1;
		int right = _Height(root->_right) + 1;

		return (left > right) ? left : right;
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
		{
			return true;
		}
		int left = _Height(root->_left);
		int right = _Height(root->_right);

		int bf = abs(left - right);
		if (bf > 1)
		{
			return false;
		}

		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}
	void _RotateL(Node* parent)
	{
		Node *subR = parent->_right;
		Node *subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;

		}
		subR->_left = parent;
		subR->_parent = parent->_parent;
		parent->_parent = subR;
		parent = subR;
		//連爸爸:)
		if (parent->_parent == NULL)
		{
			_root = parent;
		}
		else
		{
			if (parent->_parent->_key < parent->_key)
			{
				parent->_parent->_right = parent;
			}
			else
			{
				parent->_parent->_left = parent;
			}
		}
	}
	void _RotateR(Node* parent)
	{
		Node *subL = parent->_left;
		Node *subLR = subL->_right;
		parent->_left = subLR;
		if (subLR != NULL)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		subL->_parent = parent->_parent;
		parent->_parent = subL;
		parent = subL;
		if (parent->_parent == NULL)
		{
			_root = parent;
		}
		else
		{
			if (parent->_parent->_key < parent->_key)
			{
				parent->_parent->_right = parent;
			}
			else
			{
				parent->_parent->_left = parent;
			}
		}
	}
	void _InOrder(Node*& root)
	{
		if (root == NULL)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

protected:
	Node* _root;
};

void TestRBTree1()
{
	RBtree t1;

	int a[10] = { 5, 2, 9, 6, 7, 3, 4, 0, 1, 8 };
	for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		t1.Insert(a[i], i);
		t1.InOrder();
	}
	cout << "IsBalanceTree ? "<< t1.IsBalanceTree() << endl;
}

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

文章名稱：RBTree（紅黑樹）--C++-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://weahome.cn/article/ijipi.html