c/c++语言开发共享C++详细实现红黑树流程详解

//枚举红黑颜色  enum colour   {  	red,  	black,  };  //定义红黑树结点结构  template<class k,class v>  struct rbtreenode   {  	//构造  	rbtreenode(const pair<k, v>& kv = {0,0})  		:_left(nullptr)  		, _right(nullptr)  		, _parent(nullptr)  		, _kv(kv)  		,_col(black)  	{ }  	//定义三叉链  	rbtreenode<k, v>* _left; //左孩子  	rbtreenode<k, v>* _right;//右孩子  	rbtreenode<k, v>* _parent;  //父亲  	pair<k, v> _kv;  //pair对象  	//节点的颜色  	colour _col;  //定义枚举变量  };  //定义红黑树  template<class k, class v>  class rbtree   {  		typedef rbtreenode<k, v> node;  	public:  		//构造  		rbtree()   			:_root(nullptr)  		{}  	private:  		node* _root;  //定义树的根节点  };  

pair<node*, bool> insert(const pair<k, v>& kv)  {  	if (!_root) //空树处理  	{  		_root = new node(kv);  		_root->_col = black;  		return { _root, true };  	}  	//二叉搜索树的插入逻辑  	node* cur = _root, * parent = nullptr;  	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 { cur, false }; //插入失败  		}  	}  	cur = new node(kv);  	cur->_col = red;  //新增结点颜色默认设置为red  	//判断插入结点是否在parent的左边或者右边  	if (parent->_kv.first > kv.first)  //左边  	{  		parent->_left = cur;  		cur->_parent = parent;  	}  	else     //右边	  	{  		parent->_right = cur;  		cur->_parent = parent;  	}  	/* 红黑树性质处理：  		如果这棵树一开始是符合红黑树的性质，但在新增结点之后，  		导致失去了红黑树的性质，这里需要控制结点的颜色和限制  		每条路径上黑色结点的个数，以上情况都要处理      */  	while (parent && parent->_col == red) //父亲存在且父亲为红色  	{  		node* grandfather = parent->_parent;  //祖父  		//父亲出现在祖父的左边需要考虑的情况  		if(parent == grandfather ->left)  		{  			//1、uncle存在，uncle为红色  			/*  			   如果parent和uncle都存在并且都为红色这是情况一，  			   需要将parent和uncle的颜色变成红色，祖父颜色变成黑色  			   更新cur、parent、grandfather、uncle 继续向上调整  			*/  			//2、uncle不存在  			/*  这里考虑两种旋转情况，直线单旋转，折线双旋  				/*  					cur出现在parent的左边 ,右单旋转  					经过右单旋后，parent去做树的根,祖父做为右子树  					//调节结点颜色  					parent->_col = black;  					grandfather->_col = red;  				*/  				/*  					cur出现在parent的右边，左右双旋  					经过双旋后，cur作为树的根，grandfather为右子树  					调节结点颜色  					cur->_col = black;  					grandfather->_col = red;    				*/  			*/   		}  		else  //父亲出现在祖父的右边  		{  			node* uncle = grandfather->_left; //叔叔在左子树   			/*  			情况一：叔叔存在，且叔叔和父亲都是红色，那么就需要将父亲  			和叔叔结点的颜色变成黑色，再将祖父的颜色变成红色，  			继续向上调整，更新孩子、父亲、祖父、叔叔的位置  			*/  			/*  				情况二：叔叔不存在  				/*  				 	1、新增结点出现在父亲的右边，直线情况，左单旋处理  				 	旋转完后parent去做父亲的根，grandfather做父亲  				 	的左子树  							//调节颜色，根为黑，左右孩子为红  					2、新增结点出现在父亲的左边，会出现折现的情况，  					引发双旋，旋转完后，cur变成根，  					parent和grandfaher去做cur的左右孩子  						   //调节颜色,根结点为黑，左右孩子为红  				*/  			*/	  		}  	}  	//如果父亲不存在为了保证根结点是黑色的，这里一定得将根结点处理为黑色  	_root->_col = black;  }

//1、父亲一定存在的情况，叔叔存在/不存在 父亲叔叔结点颜色为红色  while (parent && parent->_col == red) //父亲存在且父亲为红色  {  	node* grandfather = parent->_parent;  //祖父  	//如果父亲和叔叔结点颜色都是红色  	if (parent == grandfather->_left)    	{  		node* uncle = grandfather->_right;    		if (uncle && uncle->_col == red)  //对应情况：uncle存在且为红  		{  			//处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整  			uncle->_col = parent->_col = black;   			grandfather->_col = red;  			//向上调整  			cur = grandfather;  //调整孩子  			parent = cur->_parent;//调整父亲  		}  		else   //uncle不存在，uncle存在且为黑  		{  			//直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，  			//旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色  			if (parent->_left == cur)   			{  				rotater(grandfather);  				parent->_col = black;  				grandfather->_col = red;  			}  			else  //parent->_right == cur   			{	  				//折线情况(cur在parent的右边)：这里会引发双旋  				rotatel(parent);  //以parent为旋转点进行左单旋  				rotater(grandfather); //以grandfather为旋转点进行右单旋转  				//旋转完后cur会去做树的根，那么设置为黑色，  				//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红  				cur->_col = black;  				grandfather->_col = red;  //黑色	结点个数相同  			}  		}  	}  	else //父亲在右子树  	{  			node* uncle = grandfather->_left; //叔叔在左子树   			if (uncle&& uncle->_col == red)  //情况一处理：叔叔存在，且叔叔的颜色是红色的（包含了父亲的颜色是红色的情况）  			{  				//根据情况一处理即可：叔叔和父亲变黑，  				//祖父变红(目的是为了每条路径的黑色结点个数相同)，继续向上  				cur = grandfather;  //孩子  				parent = cur->_parent;//父亲  			}  			else //叔叔不存在   			{  				if (cur == parent->_right)  //新增结点在父亲的右边，直线情况左单旋处理  				{  					//左单旋转，以grandfather为旋转点，旋转完后parent去做新的根，grandfather去做左子树  					rotatel(grandfather);  					//调节颜色  					grandfather->_col = red;  					parent->_col = black;  				}  				else //新增结点在父亲的左边，折线情况，引发双旋  				{  					//处理：以parenrt为旋转点做右单旋，再以grandfather为旋转点做左单旋  					rotater(parent);  //右旋  					rotatel(grandfather); //左旋  					parent->_col = grandfather->_col = red;  					cur->_col = black;  				}  				break;  			}  		}  	_root->_col = black;  }

node* uncle = grandfather->_right;    if (uncle && uncle->_col == red)  //对应情况：uncle存在且为红  {  	//处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整  	uncle->_col = parent->_col = black;   	grandfather->_col = red;  	//向上调整  	cur = grandfather;  //调整孩子  	parent = cur->_parent;//调整父亲  }

else   //uncle不存在，uncle存在且为黑  {  	//直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，  	//旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色  	if (parent->_left == cur)   	{  		rotater(grandfather);  		parent->_col = black;  		grandfather->_col = red;  	}  	else  //parent->_right == cur   	{	  		//双旋转  	}  }  

//折线情况(cur在parent的右边)：这里会引发双旋  rotatel(parent);  //以parent为旋转点进行左单旋  rotater(grandfather); //以grandfather为旋转点进行右单旋转  //旋转完后cur会去做树的根，那么设置为黑色，  //为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红  cur->_col = black;  grandfather->_col = red;   

void rotater(node* parent) //右单旋  	{  		node* subl = parent->_left;  		node* sublr = subl->_right;  		parent->_left = sublr;  		if (sublr) sublr->_parent = parent;  //防止sublr为nullptr  		subl->_right = parent;  		node* parent_parent = parent->_parent; //指针备份  		parent->_parent = subl;  		if (_root == parent) //如果parent就是树的根   		{  			_root = subl;  //subl取代parent  			_root->_parent = nullptr;  		}  		else  //如果parent并不是树的根  		{  			if (parent_parent->_left == parent) parent->_left = subl;  			else parent_parent->_right = subl;  			subl->_parent = parent_parent; //subl去做parent_parent的孩子  		}  	}  	//左单旋  	void rotatel(node* parent)  	{  		node* subr = parent->_right;  		node* subrl = subr->_left;  		parent->_right = subrl;  		if (subrl) subrl->_parent = parent;  		subr->_left = parent;  		node* parent_parent = parent->_parent;  		parent->_parent = subr;  		if (_root == parent)  		{  			_root = subr;  			_root->_parent = nullptr;  		}  		else  		{  			if (parent_parent->_left == parent) parent_parent->_left = subr;  			else parent_parent->_right = subr;  			subr->_parent = parent_parent;  		}  	}

/*  	红黑树的几点性质在于：  	1、根结点必须是红色的  	2、不会出现连续的红色结点  	3、所有路径的黑色结点个数是相同的  */  bool _checkblance(node* root, int isblacknum, int count)   {  	if (!root)   	{  		if (isblacknum != count)   		{  			printf("黑色结点个数不均等n");  			return false;  		}  		return true; //遍历完整棵树，如果以上列举的非法情况都不存在就返回true  	}  	//检查是否出现连续的红色结点  	if (root->_col == red && root->_parent->_col == red)   	{  		printf("出现了连续的红色结点n");  		return false;  	}   	//走前序遍历的过程中记录每一条路径黑色结点的个数  	if (root->_col == black) count++;  	//递归左右子树  	return _checkblance(root->_left, isblacknum, count) &&   			_checkblance(root->_right, isblacknum, count);  }  //验证红黑树  bool checkblance()  {  	if (!_root) return true;  //树为null  	//根结点是黑色的  	if (_root->_col != black)   	{  		printf("根结点不是黑色的n");  		return false;  	}  	//每一条路径黑色结点的个数必须是相同的，  	int isblcaknum = 0;  	node* left = _root;   	while (left)   	{  		if (left->_col == black) isblcaknum++; // 统计某一条路径的所以黑色结点个数  		left = left->_left;  	}  	//检查连续的红色结点，检查每一条路径的黑色结点个数是否相等  	return _checkblance(_root, isblcaknum ,0);  }