RBTree--红黑树

1.红黑树的概念

红黑树是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或者Black。通过对任何一条从根到叶子节点的路径上，各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

红黑树也是三叉链结构，如下图所示。不过它没有平衡因子，取之代之的是颜色。

2.红黑树的性质

1）红黑树中的每个节点不是红色就是黑色；

2）根节点是黑色的；

3）如果一个节点是红色的，则该节点的两个孩子节点都是黑色的，即没有连续的红色节点；

4）对于每个节点，从该节点到其所有后代节点的简单路径上，均包含形态数目的黑色节点；

5）每个叶子节点都是黑色的(此处的叶子节点指的是空结点)。

红黑树中要求最长路径不超过最短路径的2倍，是通过颜色来控制的。由红黑树的性质可知，红黑树的根节点是黑色的、每条路径上都有相同数量的黑色节点、没有连续的红色节点，那么红黑树中最短的路径就是全黑色节点的路径，最长路径是黑色节点+相同数量的红色节点，即一黑一红间隔的路径。

3.红黑树节点的定义

enum Colour
{
	BLACK,
	RED,
};

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

4.红黑树的插入操作

4.1 红黑树插入操作分析

红黑树是在二叉树搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1.按照二叉搜索树的规则插入新节点；

2.新节点插入后，检测红黑树的性质是否被破坏，因为新节点的默认颜色是红色。因此，如果其双亲节点的颜色是黑色，没有违反红黑树的任何性质，则不需要进行调整。但是当新插入节点的父亲节点的颜色为红色时，就违反了红黑树性质3不能存在连续的红色节点。此时，需要对红黑树分情况来讨论。

为什么默认新插入的节点为红色？因为插入新节点时，就涉及破坏规则2(红黑树中没有连续的红节点);还是规则3(红黑树每条路径都有相同数量的黑节点)。
首先，插入红色节点时，不一定会破坏规则2(如果插入节点的父亲节点是黑色节点)；即使破坏了规则2，新插入的节点是红色节点也只会影响一条路径。
如果新插入的节点是黑色的，会影响二叉树的所有路径，因为红黑树的每条路径都要有相同数量的黑色节点。故默认新插入的节点为红色。

约定：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点。

情况1：cur为红，p为红，g为黑(此时，p为红，则g肯定为黑)，u存在且为红。

解决方式：将p和u改为黑色，g改为红色，然后将g当成cur，继续向上调整。

注意：这里所看到的树，可能是一棵完整的树，也可能是一棵子树。如下图所示，将节点p和u改为黑色，将节点g改为红色。

①如果g是根节点，调整完成后，需要将g改为黑色。

②如果g是子树，g一定有双亲节点，且g的双亲节点如果为红色，需要继续向上调整。

情况2：cur为红，p为红，g为黑，u不存在/u存在且为黑。

此时，u的情况有两种：

1.u节点不存在，此时cur一定为新插入的节点，如果cur不是新插入的节点，则cur和p一定有一个节点的颜色是黑色，此时就不满足性质4(每条路径黑色节点的个数相同)。

a）u不存在的情况比较简单，假如p是g的左子树，cur是p的左子树，将节点g右单旋，p变黑，g变红。

b）假如p是g的右子树，cur是p的右子树，将节点g左单旋，p变黑，g变红。

2.如果u节点存在，则其颜色一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是cur的子树在调整的过程中将cur节点的颜色由黑色改为红色。则可知该情况是由情况1向上调整时转化而来。如下图所示。

a）u存在且为黑，当p为g的左孩子、cur为p的左孩子，则节点g进行右单旋，p变黑、g变红。抽象图如下：

具象图如下：

b）u存在且为黑，当p是g的右子树，cur是p的右子树时，g左单旋，p变黑，g变红。抽象图如下。

具象图如下：

情况3：cur为红，p为红，g为黑，u不存在/u存在且为黑

a）p为g的左孩子，cur为p的右孩子，则针对p做左单旋，转换成了情况2。

b）p为g的右孩子，cur为p的左孩子，则针对p做右单旋，转换成了情况2。

4.2 红黑树插入操作代码

bool Insert(const pair<K, V>& kv)
{
	//1、按二叉搜索树的规则插入节点
	//如果二叉树为空，则将新插入的节点作为根节点
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;//红黑树的根节点为黑色
		return true;
	}
		
	Node* cur = _root;
	Node* parent = nullptr;
	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
		{
			return false;
		}
	}

	cur = new Node(kv);
	if (kv.first > parent->_kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}

	//cur->_col = RED;
	//这里默认新插入的节点是红色节点，为什么呢？
	//因为插入新节点时，就涉及破坏规则2(红黑树中没有连续的红节点);还是规则3(红黑树每条路径都有相同数量的黑节点)。
	//首先，插入红色节点时，不一定会破坏规则2(如果插入节点的父亲节点是黑色节点)；即使破坏了规则2，新插入的节点是
	//红色节点也只会影响一条路径。
	//如果新插入的节点是黑色的，会影响二叉树的所有路径，因为红黑树的每条路径都要有相同数量的黑色节点。

	//情况1：cur节点为红色、parent节点为红色、grandfather为黑色、uncle节点存在且为红色；
	//情况2：uncle节点不存在
	//情况3：uncle节点存在且为黑
	while (parent&&parent->_col==RED)
	{
		//cur节点的父亲节点parent是红色，此时parent节点不可能是根节点
		//此时看cur节点的叔叔节点uncle的颜色。
		Node* grandfather = parent->_parent;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//如果grandfather不是根节点，继续往上处理。
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//情况3：双旋；先parent节点左旋，转换为情况2
				if (parent->_right == cur)
				{
					RotateL(parent);
					swap(parent, cur);
				}

				//情况2：情况2也可能是情况3进行左单旋之后，需要再进行右单旋
				RotateR(grandfather);
				grandfather->_col = RED;
				parent->_col = BLACK;

				break;
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			//情况1：uncle存在、且为红
			//情况2 or 情况3：uncle不存在 or uncle存在、且为黑
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//如果grandfather不是根节点，继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//情况3
				if (cur == parent->_left)
				{
					RotateR(parent);
					swap(cur, parent);
				}

				//情况2
				RotateL(grandfather);

				grandfather->_col = RED;
				parent->_col = BLACK;
			}
		}
	}

	//最终将根节点变为黑色
	_root->_col = BLACK;

	return true;
}

5.红黑树节点的查找

//2、红黑树查找节点
Node* Find(const pair<K, V>& kv)
{
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}

红黑树完整代码可参考：红黑树的简单实现