C++:红黑树

//使用枚举
enum Colour
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)  //跟AVL树一样，使用parent节点是为了旋转
		,_col(RED)  //默认是红色
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//先按二叉搜索树的规矩来创建一棵二叉搜索树
		if (_root==nullptr)
		{
			_root = new Node(kv);
			//因为红黑树的根节点是黑色的
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		cur->_col = RED;//多写一步，防止写错代码。
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//创建完二叉搜索树
		//开始创建红黑树，使用颜色来判断是否需要调整
		//循环往上走，循环条件：当走到的parent不为空，并且parent是红色的
		//即我们列举是三种情况，parent都是红的，就需要重新调整
		//如果parent是黑色的，那就不需要了。直接就是一棵红黑树,不进入循环
		while (parent && parent->_col == RED)
		{
			//保存祖先节点，即g节点
			Node* grandfther = parent->_parent;
			//判断父节点是在祖先节点的哪边
			if (parent == grandfther->_left)
			{
				//父节点在左边，那么叔叔节点就在右边
				Node* uncle = grandfther->_right;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;

					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的左孩子，cur是p的左孩子，以g为轴右单旋
					if (cur == parent->_left)
					{
						//右单旋
						RotateR(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的左孩子，cur是p的右孩子.
					{
						//先以p为轴左旋转
						RotateL(parent);
						//变成情况二，再以g为轴右单旋
						RotateR(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;

					}

					break;
				}
			}
			else  //parent是在grandfther的右边
			{
				//叔叔节点就在祖先节点的左边
				Node* uncle = grandfther->_left;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;

					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的右孩子，cur是p的右孩子。
					if (cur == parent->_right)
					{
						//左单旋
						RotateL(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的右孩子，cur是p的左孩子.
					{
						//先以p为轴右旋转
						RotateR(parent);
						//变成情况二，再以g为轴左单旋
						RotateL(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;

					}

					break;
				}
			}
		}
		//最后将根节点置为黑
		_root->_col = BLACK;
		return true;
	}

	void RotateR(Node* parent)
	{

		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else  
		{
			if (ppNode->_left == parent) 
			{
				ppNode->_left = subL;

			}
			else                        
			{
				ppNode->_right = subL;
			}

			
			subL->_parent = ppNode;
		}
	}

	void RotateL(Node* parent)
	{
		
		Node* subR = parent->_right;
		Node* subRL = subR->_left;	
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}

	}

private:
		Node* _root = nullptr;
};

	void Inorder()
	{
		_Inorder(_root);
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_kv.first << ": " << root->_kv.second << endl;
		_Inorder(root->_right);
	}

	//遍历其它路径
	bool Check(Node* root, int blackNum, const int ref)
	{
		//当走到空节点后，就可以对比数量
		if (root == nullptr)
		{
			//选择打印数量，看看结果对不对
			cout << blackNum << endl;
			//如果不相等，false
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}

			return true;
		}

		//判断当前节点跟它的父亲节点是否都是红的
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}

		//如果节点是黑色的，++
		if (root->_col == BLACK)
		{
			++blackNum;
		}

		//通过递归，去遍历其它的路径
		return Check(root->_left, blackNum, ref)
			&& Check(root->_right, blackNum, ref);
	}

	bool IsBalance()
	{
		//首先看看是不是空树，空树也是红黑树
		if (_root == nullptr)
		{
			return true;
		}

		//判断根节点是否为黑色，不是黑色就false
		if (_root->_col != BLACK)
		{
			return false;
		}

		//统计某一条路径的黑色节点的数量
		int ref = 0;
		//这里选择最左边的路径
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				//当节点是黑色，就++一下
				++ref;
			}

			left = left->_left;
		}

		//去寻找别的路径上的黑色节点
		return Check(_root, 0, ref);
	}