数据结构——红黑树

enum Color//利用枚举来给红黑树配色
{
	RED,
	BLACK
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_data(data)
		, _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
	{}

	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair<K, V> _data;
	Color _color;//结点的配色
};

	bool Insert(const pair<K, V>& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_color = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data.first > data.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_data.first < data.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);//这里默认是红色结点
		if (parent->_data.first > data.first)
		{
			cur->_parent = parent;
			parent->_left = cur;
		}
		else if (parent->_data.first < data.first)
		{
			cur->_parent = parent;
			parent->_right = cur;
		}
		//如果父节点为空就代表cur是根节点，没必要调整了
		//还要判断cur结点是否与父节点的颜色均为红色
		while (parent && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;//祖父结点
			if (parent == grandfather->_left)//新增结点在祖父左
			{
				Node* uncle = grandfather->_right;
				//情况一
				if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在
				{
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;
					cur = grandfather;//最后让cur等于祖父结点的位置
					parent = cur->_parent;
				}
				else
				{
					if (parent->_left == cur)//情况二
					{
						RotateR(grandfather);//右单旋
						grandfather->_color = RED;
						parent->_color = BLACK;
					}
					else if (parent->_right == cur)//情况三
					{
						RotateL(parent);//左单旋
						RotateR(grandfather);//右单旋
						cur->_color = BLACK;
						grandfather->_color = RED;
					}
					break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环
				}
			}
			else//新增结点在祖父右
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_color == RED)//情况一
				{
					uncle->_color = BLACK;
					parent->_color = BLACK;
					grandfather->_color = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else {
					if (cur == parent->_right)//情况二
					{
						RotateL(grandfather);
						grandfather->_color = RED;
						parent->_color = BLACK;
					}
					else if (cur == parent->_left)//情况三
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_color = BLACK;
						grandfather->_color = RED;
					}
					break;
				}
			}
		}
		_root->_color = BLACK;
		return true;
	}
	void RotateL(Node* parent)//左单旋
	{
		Node* pparent = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (pparent)
		{
			if (pparent->_left == parent)
				pparent->_left = subR;
			else
				pparent->_right = subR;
		}
		else
		{
			_root = subR;

		}
		subR->_parent = pparent;
	}
	void RotateR(Node* parent)//右单旋
	{
		Node* pparent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

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

	bool _IsBalanceTree(Node* root, int k, int sum)//验证
	{
		if (root == nullptr)
		{
			if (k == sum)//这里代表当前路径点和最左边的路径点相同
				return true;
			else
			{
				cout << "每条路径上黑色结点数量不同" << endl;
			}
			return false;
		}
		if (root->_color == BLACK)
			k++;
		if (root->_parent && root->_parent->_color == RED && root->_color == RED)
		{
			cout << root->_parent->_data.first << endl;
			return false;
		}
		return _IsBalanceTree(root->_left, k, sum)&&_IsBalanceTree(root->_right, k, sum);
	}