超详细红黑树的模拟实现

	enum Colour	//枚举出颜色
	{
		RED,		//红色
		BLACK		//黑色
	};

	//结点类
	template<class K, class V>
	struct RBTreeNode
	{
		//指针域
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;


		pair<K, V> _kv;	//数据域
		Colour _Col;


		RBTreeNode(const pair<K, V>& kv)//构造函数
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _kv(kv)
			, _Col(RED)				//注意这里，默认新构造的结点是红色的
		{}
	};

	//红黑树的结构
	template<class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
	
		// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
		//此版本红黑树对于重复元素，插入失败
		bool Insert(const pair<K, V>& kv);
		
		// 搜索红黑树中是否存在值为data的节点。
		//存在返回该节点的地址，不存在则返回nullptr
		Node* Find(const pair<K, V>& data);
		
		// 获取红黑树最左侧节点
		Node* LeftMost();
		// 获取红黑树最右侧节点
		Node* RightMost();
		
		//（这里的玩法大家应该不陌生了）	
		int Height();//计算红黑树的高度
		bool IsValidRBTRee();// 检测红黑树是否为有效的红黑树
	private:
		bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);
		int Height(Node* root);
		// 左单旋
		void RotateL(Node* pParent);
		// 右单旋
		void RotateR(Node* pParent);
		// 为了操作树简单起见：获取根节点
		Node*& GetRoot();
	private:
		Node* _root = nullptr;
	};

//插入函数
template<class K, class V>
bool RBTree<K, V>::Insert(const pair<K, V>& kv) {
}

//第一次插入
	if (_root == nullptr) {
		_root = new Node(kv);
		_root->_Col = BLACK;		//注意根节点一定是黑色的，默认构造的新节点是红色的，所以这里要改一下。
		return true;
	}

	//寻找插入位置
	while (cur) {
		parent = cur;
		if (_root->_kv.first > kv.first) {
			cur = cur->_left;		//插入的值当前结点的值小，往左走
		}
		else if (_root->_kv.first < kv.first) {
			cur = cur->_right;		//插入的值当前结点的值大，往右走
		}
		else {
			return false;	//本篇实现的红黑树，对于重复值，插入失败
		}
	}
	//判断插入在左边还是右边
	cur = new Node(kv);
	if (kv.first < parent->_kv.first) {				//插入在左边
		parent->_left = cur;
	}
	else {									//插入在右边
		parent->_right = cur;
	}
	cur->_parent = parent;					//保证三叉链的关系

bool Insert(const T& kv) {
	if (_root == nullptr) {
		_root = new Node(kv);
		_root->_Col = BLACK;		//注意根节点一定是黑色的，默认构造的新节点是红色的，所以这里要改一下。
		return true;
	}

	Node* cur = _root, * parent = nullptr;
	//寻找插入位置
	while (cur) {
		parent = cur;
		if (_root->_kv.first > kv.first) {
			cur = cur->_left;
		}
		else if (_root->_kv.first < kv.first) {
			cur = cur->_right;
		}
		else {
			return false;
		}
	}
	//判断插入在左边还是右边
	cur = new Node(kv);

	if (kv.first < parent->_kv.first) {				//插入在左边
		parent->_left = cur;
	}
	else {									//插入在右边
		parent->_right = cur;
	}
	cur->_parent = parent;					//保证三叉链的关系
	
	//
	while (parent && parent->_Col == RED) {
		//爷爷结点
		Node* grandfather = parent->_parent;

		if (parent == grandfather->_left) {			//如果父亲是爷爷的左孩子
			Node* uncle = grandfather->_right;		//那么叔叔就是爷爷的右孩子

			//叔叔存在且为红
			if (uncle && uncle->_Col == RED) {
				//变色
				uncle->_Col=parent->_Col = BLACK;
				grandfather->_Col = RED;

				//继续向上更新
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else {									//叔叔不存在或者 存在且为黑
				if (cur == parent->_left) {			
					//			g
					//		p
					//c
					RotateR(grandfather);
					grandfather->_Col = RED;
					parent->_Col = BLACK;
				}
				else {
					//		g
					//	p
					//		c
					RotateL(parent);
					RotateR(grandfather);
					cur->_Col = BLACK;
					grandfather->_Col = RED;
				}
				break;	//此时最顶端的结点已经变成黑色了，不需要继续向上更新了。
			}
		}
		else {		// 如果父亲是爷爷的右孩子
			Node* uncle = grandfather->_left;		//那么叔叔就是爷爷的左孩子

			//叔叔存在且为红
			if (uncle && uncle->_Col == RED) {
				//变色
				uncle->_Col = parent->_Col = BLACK;
				grandfather->_Col = RED;

				//继续向上更新
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else {									//叔叔不存在或者 存在且为黑
				if (cur == parent->_left) {
					//	g
					//		p
					//	c
					//注意旋转时的传参
					RotateR(parent);
					RotateL(grandfather);
					grandfather->_Col = RED;
					cur->_Col = BLACK;
				}
				else {
					//	g
					//		p
					//			c
					RotateL(grandfather);		//注意旋转时的传参
					
					parent->_Col = BLACK;
					grandfather->_Col = RED;
				}
				break;	//此时最顶端的结点已经变成黑色了，不需要继续向上更新了。
			}
		}
	}
	_root->_Col = BLACK;		//最后根节点一定是黑的
	return true;

}

	// 获取红黑树最左侧节点
	template<class K, class V>
	typename RBTree<K, V>::Node* RBTree<K, V>::LeftMost() {
		Node* left_most = _root;
		while (left_most->left) {
			left_most = left_most->left;
		}
		return left_most;
	}

	// 获取红黑树最右侧节点
	template<class K, class V>
	typename RBTree<K, V>::Node* RBTree<K, V>::RightMost() {
		Node* right_most = _root;
		while (right_most->right) {
			right_most = right_most->left;
		}
		return right_most;
	}

// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
template<class K, class V>
bool  RBTree<K, V>::IsValidRBTRee() {
	if (_root == nullptr)	//空树也是红黑树
		return true;

	if (_root->_Col != BLACK)	//根节点必须是红黑树
	{
		return false;
	}

	// 基准值
	int pathBlack = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_Col == BLACK)
			++pathBlack;
		cur = cur->_left;
	}
	_IsValidRBTRee(_root, 0, pathBlack);
}


template<class K, class V>
bool RBTree<K, V>::_IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {


	if (pRoot == nullptr)
	{
		if (blackCount != pathBlack)		//一条路径走到底，也就是走到叶子结点以后，判断这条路径上的黑色结点个数（blackCount）是否与 设定的黑色结点个数相同（pathBlack）
			return false;
		return true;
	}


	if (pRoot->_Col == BLACK)
	{
		++blackCount;
	}


	if (pRoot->_Col == RED && pRoot->_parent && pRoot->_parent->_Col == RED)
	{
		cout << _root->_kv.first << "出现连续红色节点" << endl;
		return false;
	}

	//递归访问左右子树
	return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
		&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
}

	template<class K, class V>
	typename RBTree<K, V>::Node*& RBTree<K, V>::GetRoot() {
		return _root;
	}

	template<class K, class V>
	int RBTree<K, V>::Height()
	{
		return Height(_root);
	}
	template<class K, class V>
	int RBTree<K, V>::Height(typename RBTree<K, V>::Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = Height(root->_left);	//计算左子树的高度
		int rightHeight = Height(root->_right);	//计算右子树的高度
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

template<class K, class T,>
typename RBTree<class K, class T, class Of_T>::Node* RBTree<class K, class T, class Of_T>::Find(const T& data) {
	Node* cur = _root;
	while (cur)
	{
		if (data > cur->_data)
		{
			cur = cur->_right;
		}
		else if (data < cur->_data)
		{
			cur = cur->_left;
		}
		else return cur;
	}
	return nullptr;  // 找不到目标元素时返回nullptr
}