RBTree（红黑树）--C++

红黑树是满足下面性质的二叉搜索树

1. 每个节点，不是红色就是黑色的

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个子节点是黑色的

4. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

#pragma once enum Color{ RED, BLACK }; template<class K, class V> 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<K, V>* _left;	RBtreeNode<K, V>* _right;	RBtreeNode<K, V>* _parent;	K _key;	V _vlaue;	Color _col; }; template<class K, class V> class RBtree {	typedef RBtreeNode<K, V> 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;	}	//调色	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<int, int> 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; }