红黑树介绍

一、介绍

通过红色和黑色以及一系列规则让红黑树的最长路径不超过最短路径的2倍。

由于高度控制没有AVL树严格，所以旋转比AVL树少。

规则：

1、根节点是黑色

2、红色节点的孩子一定是黑色（不能出现连续的红色）

3、对于每一个节点，从该节点到其所有后代的简单路径上均包含相同的黑色节点（每条路径的黑色节点数量相同）

4、每个叶子节点都是黑色（此处的叶子节点指空节点）

二、插入节点

首先我们要明白一开始插入的节点是红色不是黑色，因为插入黑色一定会破坏规则3，而且是得罪了每条路径，因为一开始每条路径黑色节点数量一样，你在一条路径上插入黑色节点，导致全部路径都不符合规则3，修改很麻烦，所以我们选择插入红色节点，可能会破坏规则2（当父节点是红色）一定不会破坏规则3

所以现在我们分析出了需要特殊处理的情况：插入 cur 节点是红色，其父亲 parent 是红色时破坏了规则2需要处理。

再深入分析：由于父亲节点以及向上的节点全部合法，所以父亲是红色，祖父一定存在并且是黑色，而要使以祖父为起始点的所有路径上黑色节点数量相同就要看叔叔的情况。

至此我们就已经分析清楚要处理的情况：父亲 parent，cur，祖父 g 的颜色是确定的，分别是红，红，黑，只有叔叔 uncle 不确定

1、叔叔存在且为红

（1）第一步：父亲叔叔全为黑，祖父红

这样既没有连续的红色，也保证了黑色节点相同。

（2）第二步：向上检查

由于祖父在第一步变成了红色，会引发三种情况：

2、叔叔不存在或叔叔存在且为黑

四种情况（图中是叔叔存在且为黑，叔叔不存在也一样，不影响代码编写）：

（1）cur 左，parent 左

（2）cur 右，parent 左

（3）cur 右，parent 右

（4）cur 左，parent 右

三、插入总结

循环处理连续的红色（cur 红，parent 红）直到父亲不存在（cur 是根）或父亲是黑色时才会停止循环处理。

连续红色的处理情况其实就2种大情况，5种小情况需要处理：

1、叔叔存在且为红

2、叔叔不存在或叔叔存在且为黑

（1）cur 左，parent 左

（2）cur 右，parent 左

（3）cur 右，parent 右

（4）cur 左，parent 右

四、插入代码展示

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;
	// 1.像搜索二叉树一样插入节点cur
	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);
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;

	// 新插入是红色，如果父亲是黑色就没事
	while (parent && parent->_col == RED)
	{
		Node* g = parent->_parent;
		Node* uncle = parent == g->_left ? g->_right : g->_left;
		// 情况一：叔叔存在且为红，u p 变黑，g变红，向上
		if (uncle && uncle->_col == RED)
		{
			uncle->_col = parent->_col = BLACK;
			g->_col = RED;
			cur = g;
			parent = cur->_parent;
		}
		// 情况二：叔叔存在且为黑或叔叔不存在
		else
		{
			// u parent cur 的位置决定的是左右单旋双旋
			
			//       gB              pB
			//    pR     u   ->   cR     gR
			// cR                            u
			if (cur == parent->_left && parent == g->_left)
			{
				RotateR(g);
				parent->_col = BLACK;
				g->_col = RED;
			}
			//       gB              gB            cB
			//    pR     u   ->   cR     u  ->  pR    gR
			//       cR         pR                       u
			else if (cur == parent->_right && parent == g->_left)
			{
				RotateL(parent);
				RotateR(g);
				cur->_col = BLACK;
				g->_col = RED;
			}
			//       gB                pB
			//     u    pR    ->    gR    cR
			//             cR     u                        
			else if (cur == parent->_right && parent == g->_right)
			{
				RotateL(g);
				g->_col = RED;
				parent->_col = BLACK;
			}
			//       gB             gB                 cB
			//    u     pR   ->   u    cR     ->    gR    pR
			//       cR                   pR      u                  
			else if (cur == parent->_left && parent == g->_right)
			{
				RotateR(parent);
				RotateL(g);
				cur->_col = BLACK;
				g->_col = RED;
			}
			else
				assert(false);
			break;
		}
	}

	_root->_col = BLACK;

	return true;
}

五、验证红黑树

就是验证四条规则

// 检查：先找到任意一条路径的黑色节点数量，再检查每条路径黑色节点个数是否一样
bool IsBalance()
{
	// 检查规则二：根节点是黑色
	if (_root->_col == RED)
	{
		return false;
	}
	// 统计黑色节点个数
	int refNum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refNum;
		}

		cur = cur->_left;
	}

	return Check(_root, 0, refNum);
}

bool Check(Node* root, int blackNum, const int refNum)
{
	// 到一条路径的结尾，检查规则四：每一条路径上黑色节点个数一样
	if (root == nullptr)
	{
		//cout << blackNum << endl;
		if (refNum != blackNum)
		{
			cout << "存在黑色节点的数量不相等的路径" << endl;
			return false;
		}

		return true;
	}

	// 检查规则三：不能出现连续红节点
	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);
}