c++ 红黑树的插入

#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);	} };