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

創(chuàng)新互聯(lián)公司是一家專注于成都做網(wǎng)站、成都網(wǎng)站建設(shè)與策劃設(shè)計(jì),宜秀網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:宜秀等地區(qū)。宜秀做網(wǎng)站價(jià)格咨詢:18982081108

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)的簡單路徑上，均包含相同數(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;
}