手写红黑树

前言

所有的图片挂载于github，如不能查看，请检查网络信息。

文章主要进行红黑树的代码实现与原理阐释，对于基础的数据结构概念，本文不再做详细解释。

由于时间原因，实现原理与实现方式会直接以代码+注释的形式给出

什么是红黑树

在所有的数据结构中，存储类数据结构所面临的问题一直有两个：排序和查找。

前者表示了数据结构的设计是否是有序的，对于很多业务需求来说，排序是刚需，如何保证数据不断地增减、修改的情况下，仍保持有序，是对数据结构的基本需求。后者则是出于性能上的考虑，当数据量足够大的时候，如果查找时间虽数据量线性增长，那显然也是不可接受的。

基于这两点，我们提出非一维的数据结构，例如树状结构、图状结构。并且，提供了一套完整的方案来进行数据的处理。

鉴于代码实现的简单性与查找的便利性（一次查询需要排除尽可能多的非法数据），我们提出一种二叉树结构，在此基础上，又提出了平衡树、搜索树结构。

而红黑树，就是一颗近似二叉搜索平衡树。他可以以O（logn）的时间复杂度，完成数据的增删改查。

在实现红黑树之前，我们先来复习一下红黑树的数据结构约定：

1.所有节点都是红色或者黑色节点

2.根节点一定为黑色节点

3.叶子结点也一定为黑色节点（可以为NIL）

4.从任意一个节点出发，其所有的完整路径黑高相等

5.红色节点不能相邻（不能有父子关系）

现在，我们正式开始实现红黑树

构建红黑树节点

首先，是构建节点，我们需要定义节点的基础数据结构，包含颜色、数据内容、父子指针的定义，完整内容如下：

#define RED 0
#define BLACK 1
#define NOCOLOR 2

enum color
{
	red = RED,
	black = BLACK,
	noclor=NOCOLOR
};

struct rb_node
{
	color color = red;
	TVal val;
	rb_node* parent = nullptr;
	rb_node* left = nullptr;
	rb_node* right=nullptr;
};

然后，我们需要构造析构函数，包括树的构造析构与节点的构造析构。

	rbtree()
	{
		int a = 0;
		rb_node *newnode = buyNode(a);
		NIL = newnode;
		NIL->color = black;
		_root_node = NIL;
	}
	virtual ~rbtree()
	{
		destroy(_root_node);
		delete Nil; Nil = nullptr;
	}

	void destroy(rb_node*& root)
	{
		if (root == NIL)
		{
			return;
		}
		if (root->left != NIL)
		{
			destroy(root->left);
		}
		if (root->right != NIL)
		{
			destroy(root->right);
		}
		delete root;
		root = NULL;
	}

节点本身的构造析构使用缺省的就可以，无需浪费时间，但是我们需要再红黑树这个类里面进行节点的构造，所以单独写一个函数。具体内容如下：

	rb_node* buyNode()
	{
		int val = 0;
		return buyNode(val);
	}
	rb_node* buyNode(const TVal& ival = TVal())
	{
		using pNode = rbtree<TVal>::rb_node;
		pNode *pnode = new rb_node();
		pnode->val = ival;
		if (NIL)
		{
			pnode->parent = NIL;
			pnode->left = NIL;
			pnode->right = NIL;
		}
		return std::move(pnode);
	}

左旋与右旋，因为左旋右旋比较简单，仅注释了容易出错的一步：

	//左旋
	void leftRotate(rb_node*& t)
	{
		if (!t)return;
		rb_node* tp = t->parent;
		rb_node* tr = t->right;
		if (tr == NIL)return;//根本没有左旋的条件
		t->right = tr->left;//这一步提前，因为后续会修改tr->left

		if (t == _root_node)//第二步是修改两个节点的父
		{
			_root_node = tr;
		}
		else
		{
			if (tp->left == t)//target node is left child
			{
				tp->left = tr; tr->parent = tp;//修改父节点
			}
			else if(tp->right == t)
			{
				tp->right = tr; tr->parent = tp;//修改父节点的关系
			}
		}

		t->parent = tr;//最后再修改两个节点之间的之间关系
		tr->left = t;
	}

	//右旋(处理当前节点与节点的左孩子)
	void rightRotate(rb_node* &t)//input target 
	{
		if (!t)return;
		rb_node* tp = t->parent;
		rb_node* tl = t->left;
		if (tl == NIL)return;

		t->left = tl->right;

		if (t==_root_node)
		{
			_root_node = tl;
		}
		else
		{
			if (tp->left==t)
			{
				tp->left = tl;
			}
			else if (tp->right==t)
			{
				tp->right = tl;
			}
		}

		t->parent = tl;
		tl->right = t;
	}

所有对于红黑树的修改都要优先置于叶子或者近似叶子节点来操作。插入的情况大致可以分为两种，即仅仅需要染色和需要调整旋转两种方式：

//插入
	void insertFix(rb_node*& t)
	{
		rb_node* tp = t->parent;
		while (t->parent->color==red)//因为插入节点是红的，不影响黑高；如果上级为黑，什么都不用干
		{
			//以下总共六个分支，需要记忆一共两种情况（直接染色+调整旋转）
			rb_node* tpp = tp->parent;//此时tpp节点应该是黑的
			if (tp== tpp->left)//当前tp是tpp左孩子
			{
				rb_node* tppr = tpp->right;//uncle节点
				if (tppr->color==red)//叔父节点与父节点同为红色
				{
					tppr->color = black;
					tp->color = black;
					tpp->color = red;
					t = tpp;
				}
				else
				{					
					if (t == tp->right)//当前节点为l-r，左旋调整一下
					{
						leftRotate(tp);
					}
					if(t == tp->left)//当前节点是左孩子[达成l-l,准备右旋]
					{
						tp->color = black;
						tpp->color = red;
						rightRotate(tpp);
					}
				}
			}
			else if (tp == tpp->right)
			{
				rb_node* tppl = tpp->left;//uncle节点
				if (tppl->color == red)//叔父节点与父节点同为红色
				{
					tppl->color = black;
					tp->color = black;
					tpp->color = red;
					t = tpp;
				}
				else
				{
					if (t == tp->left)//当前节点为r-l，右旋调整一下
					{
						rightRotate(tp);
					}
					if (t == tp->right)//当前节点是右孩子[达成r-r,准备左旋]
					{
						tp->color = black;
						tpp->color = red;
						leftRotate(tpp);
					}
				}
			}
		}
		_root_node->color = black;
	}
	void insertNode(TVal &ival)
	{
		rb_node* newnode = buyNode(ival);
		insertNode(newnode);
	}
	void insertNode(rb_node*& t)
	{
		if (_root_node==NIL)
		{
			_root_node = t; _root_node->color = black; return;
		}
		rb_node* frontpos = _root_node;//查询插入的位置（插入节点的父节点）(一定为叶子节点)
		rb_node* temp = _root_node;//temp的边界条件为nil
		while (temp != NIL)
		{
			frontpos = temp;
			if (t->val < temp->val)
				temp = temp->left;
			else
				temp = temp->right;
		}

		t->parent = frontpos;
		//我们需要决定把它插在左还是右上面
		if (t->val>frontpos->val)
		{
			frontpos->right = t;
		}
		else
		{
			frontpos->left = t;
		}

		//调整插入之后的红黑树（从插入的那个节点开始）
		insertFix(t);
	}

删除的重心在于对黑高的把握，注意在下文中的红黑树旋转的注解

	rb_node* successor(rb_node* t)
	{
		if (t->right != NIL)
		{
			rb_node* afterNode = _root_node;//这是一个叶子节点(或者单叶子节点)
			rb_node* temp = t->right;
			while (temp != NIL)
			{
				afterNode = temp;
				temp = temp->left;
			}
			return afterNode;
		}
		//要是没有右子，那么后继节点就只能寄希望于我们当前在一颗左树上
		//这棵树的父节点就是我们要的后继节点
		rb_node* tp = t->parent;
		while (tp != NIL && t == tp->right)
		{
			t = tp;
			tp = t->parent;
		}

		return tp;
	}

	void removeFix(rb_node* t)
	{
		if (t->color==red)//如果当前节点是红色的，那刚好可以弥补之前的删除节点
		{
			t->color = black;
			return;
		}
		while (t!=_root_node && t->color==black)//边界条件：从下向上，处理黑高
		{
			//前提条件是t所在的分支黑高被减一，已经不平衡了
			rb_node* tp = t->parent;//注意，此时的tp可以是红色或者是黑色，但是我们不分开讨论（剪枝）
			if(tp->left==t)
			{
				rb_node* tpr = tp->right;
				if (tpr->color==red)//这里意味着tpp当前是黑色的，父节点是黑色的不利于我们进行两颗子树的黑高调整
				{
					//当前tpr是红的，那么tprl-tprr都是黑色
					tpr->color = black;
					tp->color = red;
					leftRotate(tp);//转完之后，tprl就成为了tp的右节点

					//指向刷新
					tp= t->parent;//此时tp有了黑色的右节点
					tpr = tp->right;//tpr为黑色
				}
				//此时，虽然有t的路径上，黑高还是减一的状态，但是tpr已经是黑色的了
				if (tpr->left->color==black && tpr->right->color==black)
				{
					//如果在t的叔父上也把黑高减一，两边将重新平衡
					//因为现在已经有了一个黑三角（tpr|tprl|tprr），把父节点染红就可以了
					tpr->color = red;
					t = tp;//此刻的tp应该是红色的
				}
				else if (tpr->right->color == black)
				{
					//此时无法再在t的叔父上也把黑高整体减一，但是我们可以减去一半
					//将tpr左边的黑高减一
					tpr->color = red;
					tpr->left->color = black;
					rightRotate(tpr);//此时tpr已经不是tp的右子节点了，但是后面我们不用他了，也就不在刷新

					t = tp->right;//此时新的不平衡问题转移到了减到一半的tpr上面
				}
				else
				{
					//此时tpr可能有两个红色节点，且右节点一定是红的（rr难以组成）
					tpr->color = tp->color;//tpr的路径黑高减一（准备拆分tprr|tprl）
					tp->color = black;//整体黑高加一（为左转准备）
					tpr->right->color = black;//tprr黑高加一（它不跟着左转，所以单独加一了）

					leftRotate(tp);//tprr将会留在右边，而tprl将作为t的兄弟出现（他两黑高目前一致）
					//全部整完，黑高平衡了
					t = _root_node;
				}
			}	
			else
			{
				rb_node* tpl = tp->left;
				if (tpl->color == red)//这里意味着tpp当前是黑色的，父节点是黑色的不利于我们进行两颗子树的黑高调整
				{
					//当前tpl是红的，那么tpll-tplr都是黑色
					tpl->color = black;
					tp->color = red;
					leftRotate(tp);//转完之后，tpll就成为了tp的右节点

					//指向刷新
					tp = t->parent;//此时tp有了黑色的右节点
					tpl = tp->right;//tpl为黑色
				}
				//此时，虽然有t的路径上，黑高还是减一的状态，但是tpl已经是黑色的了
				if (tpl->left->color == black && tpl->right->color == black)
				{
					//如果在t的叔父上也把黑高减一，两边将重新平衡
					//因为现在已经有了一个黑三角（tpl|tpll|tplr），把父节点染红就可以了
					tpl->color = red;
					t = tp;//此刻的tp应该是红色的
				}
				else if (tpl->right->color == black)
				{
					//此时无法再在t的叔父上也把黑高整体减一，但是我们可以减去一半
					//将tpl左边的黑高减一
					tpl->color = red;
					tpl->left->color = black;
					rightRotate(tpl);//此时tpl已经不是tp的右子节点了，但是后面我们不用他了，也就不在刷新

					t = tp->right;//此时新的不平衡问题转移到了减到一半的tpl上面
				}
				else
				{
					//此时tpl可能有两个红色节点，且右节点一定是红的（rr难以组成）
					tpl->color = tp->color;//tpl的路径黑高减一（准备拆分tplr|tpll）
					tp->color = black;//整体黑高加一（为左转准备）
					tpl->right->color = black;//tplr黑高加一（它不跟着左转，所以单独加一了）

					leftRotate(tp);//tplr将会留在右边，而tpll将作为t的兄弟出现（他两黑高目前一致）
					//全部整完，黑高平衡了
					t = _root_node;
				}
			}
		}

	}
	void removeNode(TVal& ival)
	{
		rb_node* pNode = searchNode(ival);
		if (pNode)
		{
			removeNode(pNode);
		}
	}
	void removeNode(rb_node*& t)
	{
		//先找后继节点（删除和插入一样，需要从尽量叶子节点出发，简单一些）
		rb_node* pdeleteNode = nullptr;
		if (t->left==NIL || t->right==NIL)//t本身是叶子节点（或者是单孩子节点）
		{
			pdeleteNode = t;
		}
		else
		{
			pdeleteNode=successor(t);//此时后继节点是在t->right上面找的，所以返回的节点也是单孩子或者叶子
		}

		//现在删除的节点一定为叶子或者单孩子节点
		rb_node* pdeleteChild = (t->left == NIL) ? t->right : t->left;

		//把删除节点的子节点顶上来
		if (pdeleteNode == _root_node)
			_root_node = pdeleteNode;
		else if (pdeleteNode == pdeleteNode->parent->left)
			pdeleteNode->parent->left = pdeleteChild;
		else
			pdeleteNode->parent->right = pdeleteChild;
		pdeleteChild->parent = pdeleteNode->parent;

		//把要删除的节点的val给我们查找的那个节点（一个是要删除值，一个是要删除物理地址）
		t->val = pdeleteNode->val;

		//检测当前的行为是否会影响黑高（到目前位置，只进行了一次删除pdeleteNode）
		if (pdeleteNode->color==black)
		{
			//由于删除了一个黑色节点，我们可能会导致黑高发生变化
			//或者会导致两个红色节点相邻
			removeFix(pdeleteChild);
		}
	}

Q.E.D.