红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。红黑树要确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

红黑树的规则

• 每个结点不是红色就是黑色
• 根结点是黑色的
• 如果⼀个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点
• 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色节点

由于以上的规则，我们可以分析出极端场景下，最短路径就就是全是黑色结点的路径（假设最短路径长度为bh(black height)），最长的路径就是一黑一红间隔组成（最长路径的长度为2bh），理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。
假设任意⼀条从根到NULL结点路径的长度为x，那么bh<=h<=2bh。

红黑树的效率

• 红黑树增删查改最坏也就是走最长路径2*logN ，那么时间复杂度还是O（logN）。

• 红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡；红黑树通过4条规则的颜色约束，间接的实现了近似平衡。他们效率都是同⼀档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的实现

红黑树的结构

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)
	{ }
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:
private:
	Node* _root = nullptr;
};

红黑树的插入

红黑树插入一个值的大致过程

说明：假设我们把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

1. 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。
2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点一定会破坏规则4，而且规则4是很难维护的。
3. 非空树插入后，如果父亲结点是黑色的，则没有违反任何规则，插入结束。
4. 非空树插入后，如果父亲结点是红色的，则违反规则3。进一步分析，c是红色，p为红色，g一定是黑色，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。

情况一：变色

c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新。

跟AVL树类似，上图我们展示了一种具体情况，但是实际中需要这样处理的有很多种情况。
所以我们依旧使用抽象化表达，用d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。

但是抽象图一开始是不好理解的，我们接下来展示hb0/hb1的具体情况组合分析，来帮助我们理解


可见不论情况多少种，多么复杂，处理方式都是⼀样的，变色再继续往上处理即可，所以在理解以后我们只需要看抽象图就很明了了

情况二：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑。u不存在，则c⼀定是新增结点；u存在且为黑，则c⼀定不是新增，c之前一定是黑色的，是在c的子树中插入了新的节点，符合情况1，更新上来将c从黑色变成红色了。

与AVL树旋转相似，纯碎的一边高，用单旋可以解决。

情况三：双旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑。u不存在，则c⼀定是新增结点；u存在且为黑，则c⼀定不是新增，c之前一定是黑色的，是在c的子树中插入了新的节点，符合情况1，更新上来将c从黑色变成红色了。

与AVL树相似，不是纯碎的一边高，（如1）对于p来说，右边高，而对于g来说左边高，此时用单旋解决不了了，要使用双旋解决。

插入的具体代码实现

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = cur;
	while (cur)
	{
		if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			assert(false);
		}
	}
	cur = new Node(kv);
	cur->_kv = RED;
	if (kv.first > parent->_kv.first)
	{
		parent->_rignt = cur;
	}
	else 
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	Node* grandfather = nullptr;
	while (parent&&parent->_col == RED)
	{
		grandfather = parent->_parent;
		//    g
		//p       (u)
		if (parent = grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			//      g
		    //  p       u
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = parent->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			//u不存在或者u存在且为黑
			else
			{
				//      g
				//   p     u
				//c
				if(cur==parent->_left)
				{
					RotateR(grandfather);
					parent->_col = BLACK:
					grandfather->_col = RED;
				}
				//       g
				//   p       u
				//     c
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}

		}
		else
		//     g
		//(u)      p
		{
			Node* uncle = grandfather->_left;
			//    g
		    //u       p
			if (uncle && uncle->_col == RED)
			{
				uncle->_col = parent->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			//u不存在或者u存在且为黑
			else
			{
				//      g
				//   u      p
				//              c
				if(cur==parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK:
					grandfather->_col = RED;
				}
				//        g
				//   u         p
				//          c
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		_root->_col = BLACK;
	}
	return true;
}

红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为O(logN)

红黑树的验证

用获取最长路径和最短路径，检查最长路径不超过最短路径的2倍的方法是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，只是当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，也就⼀定能保证最长路径不超过最短路径的2倍。

1. 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色
2. 规则2直接检查根即可
3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了⼀条路径的黑色结点数量。再任意⼀条路径黑色结点数量作为参考值，依次比较即可
   

bool Check(Node* root,int blacknum, const int refnum)
{
	if (_root == nullptr)
	{
		if (refnum == blacknum)
		{
			return true;
		}
		else
		{
			cout << "存在黑色节点数量不相等的路径" << endl;
			return false;
		}
	}
	if (_root->_col == RED && _root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在连续红色节点" << endl;
		return false;
	}
	if (root->_col == BLACK)
	{
		blacknum++;
	}
	return Check(root->_left, blacknum, refnum) && Check(root->_right, blacknum, refnum);
}

bool IsBalanceTree()
{
	if (_root == nullptr)
	{
		return true;
	}
	if (_root->_col == RED)
	{
		return false;
	}
	int refnum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			cur++;
		}
		cur = cur->_left;
	}
	return Check(_root, 0, refnum);
}