【C++】红黑树的插入分析及验证

#pragma once
#include<iostream>
#include<cassert>	
using namespace std;
enum colour
{
	RED,//红色 默认为0
	BLACK,//黑色 默认为1
};
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:
	   bool insert(const pair<K, V>& kv)
	   {
		   if (_root == nullptr)
		   {
			   _root = new Node(kv);
			   _root->_col = BLACK;//若刚插入一个节点，则该节点颜色是黑色
			   return true;
		   }
		   Node* parent = nullptr;//用于记录cur的前一个节点
		   Node* cur = _root;
		   while (cur)
		   {
			   //若插入的值比当前树的值小 插入左边
			   if (cur->_kv.first > kv.first)
			   {
				   parent = cur;
				   cur = cur->_left;
			   }
			   //若插入的值比当前树的值大 插入右边
			   else if (cur->_kv.first < kv.first)
			   {
				   parent = cur;
				   cur = cur->_right;
			   }
			   else
			   {
				   //若插入的值，在树中有相同的值 ，则插入失败
				   return false;
			   }
		   }
		   cur = new Node(kv);
		   //再次判断parent当前节点值与插入值大小
		   if (parent->_kv.first > kv.first)
		   {
			   parent->_left = cur;
		   }
		   else
		   {
			   parent->_right = cur;
		   }
		   //cur的上一个节点即为 刚才的记录cur前一个节点的parent
		   cur->_parent = parent;

           //当父节点不为NULL并且父节点为红色
		   while (parent != nullptr && parent->_col == RED)
		   {
			   Node* grandfather = parent->_parent;//爷爷节点

			   //若父节点为爷爷节点的左子树，则unlce为爷爷节点的右子树
			   if (grandfather->_left == parent)
			   {
				   Node* uncle = grandfather->_right;
				   //       g
				   //    p     u
				   // c
				   //情况1:u存在并且为红，直接变色即可，并继续往上处理
				   if (uncle && uncle->_col == RED)
					   //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
				   {
					   parent->_col = BLACK;
					   uncle->_col = BLACK;
					   grandfather->_col = RED;

					   //继续往上调整
					   cur=grandfather;
					   parent = cur->_parent;
				   }
				   //情况2+3:u不存在或者u存在且为黑，旋转+变色
				   else
				   {	 
					   //情况2
					   //g p c 作为一条直线 所以为单旋
					   //    g
					   //  p   u
	 				   //c 
					   if (cur == parent->_left)
					   {
						   //右旋转
						   RotateR(grandfather);
						    
						   //最终p作为最终的根 为黑  g为红 
						   parent->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   //情况3
					   //g p c 作为一条折线 所以为双旋
					   //    g
					  //   p   u
					  //     c 
					   else
					   {
						   //左单旋
						   RotateL(parent);
						   //右单旋
						   RotateR(grandfather);
						   //最终cur作为最终的根 为黑  g为红 
						   cur->_col = BLACK;
						   grandfather->_col = RED;
						   //父节点继续保持红色
						   parent->_col = RED;
					   }
					   break; 
				   }
			   }

			   else//grandfather->_right == parent
				   ////若父节点为爷爷节点的右子树，则unlce为爷爷节点的左子树
			   {
				   //   g
				   // u   p
				   //       c
				   Node* uncle = grandfather->_left;

				   //情况1:u存在并且为红，直接变色即可，并继续往上处理
				   if (uncle && uncle->_col == RED)
					   //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
				   {
					   parent->_col = BLACK;
					   uncle->_col = BLACK;
					   grandfather->_col = RED;

					   //继续往上调整
					   cur = grandfather;
					   parent = cur->_parent;
				   }

				   //情况2+3:u不存在或者u存在且为黑，旋转+变色
				   else
				   {
					   //情况2
					   //g p c 作为一条直线 所以为单旋
					   //    g
					   //  u   p
					   //        c  
					   if (cur == parent->_right)
					   {
						   //左旋转 
						   RotateL(grandfather);

						   //最终p作为最终的根 为黑  g为红 
						   parent->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   //情况3
					   //g p c 作为一条折线 所以为双旋
					   //   g
					  //  u   p
					  //    c 
					   else
					   {
						   //右单旋
						   RotateR(parent);
						   //左单旋
						   RotateL(grandfather);
						   //最终cur作为最终的根 为黑  g为红 
						   cur->_col = BLACK;
						   grandfather->_col = RED;
					   }
					   break;
				   }
			   }
		   }
		   //为了避免grandfather节点正好为根时，会被更新成红色的情况
		   _root->_col = BLACK;
		   return true;
	   }

	   void inorder()//中序遍历
	   {
		   _inorder(_root);
		   cout << endl;
	   }
	   //判断一颗二叉树是否为红黑树
	   bool isbalance()
	   {
		   //检查根是否为黑
		   if (_root && _root->_col == RED)
		   {
			   cout << "根节点颜色是红色" << endl;
			   return false;
		   }
		   //连续的红色节点
		   return _check(_root,0);
	   }

	private:
		bool _check(Node* root,int blacknum)
		{
			if (root == nullptr)
			{
				//为空时，blacknum代表一条路径的黑色节点个数
				cout << blacknum << " ";
				return true;
		    }
			//blacknum代表黑色节点的个数
			if (root->_col == BLACK)
			{
				blacknum++;
			}
			//若当前节点为红 父节点也为红
			if (root->_col == RED
				&&root->_parent 
				&&root->_parent->_col==RED)
			{
				cout << "存在连续的红色节点" << endl;
				return false;
			}
			//遍历整棵树
			return	_check(root->_left,blacknum) && _check(root->_right,blacknum);
		}
		void _inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_inorder(root->_left);
			cout << root->_kv.first << " ";
			_inorder(root->_right);
		}
		   void RotateL(Node* parent)//左单旋
		   {
			   Node* subR = parent->_right;
			   Node* subRL = subR->_left;

			   parent->_right = subRL;
			   if (subRL != nullptr)
			   {
				   subRL->_parent = parent;
			   }
			   Node* ppnode = parent->_parent;//记录parent的前一个节点

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

			   if (ppnode == nullptr)//说明parent是根即代表整棵树
			   {
				   _root = subR;//subR作为新的根
				   _root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
			   }
			   else//说明旋转的是一部分，所以要跟ppnode相连接
			   {
				   if (ppnode->_left == parent)//若连接在左子树上
				   {
					   ppnode->_left = subR;
				   }
				   else//若连接在右子树上
				   {
					   ppnode->_right = subR;
				   }
				   subR->_parent = ppnode;//将subR父节点置为ppnode
			   }
		   }

		   void RotateR(Node* parent)//右单旋
		   {
			   Node* subL = parent->_left;
			   Node* subLR = subL->_right;
			   parent->_left = subLR;
			   if (subLR != nullptr)
			   {
				   subLR->_parent = parent;
			   }
			   Node* ppnode = parent->_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;//使subL的父节点为ppnode
			   }

		   }
	private:
		Node* _root = nullptr;
};

void test_RBTree1()
{
	int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
	RBTree<int, int>v1;
	for (auto e : a)
	{
		v1.insert(make_pair(e, e));
	}
	v1.inorder();
	cout << v1.isbalance() << endl;
	
}