红黑树特性

1.结点是黑色或红色
2.根节点是黑色
3.叶子结点是黑色的空结点
4.任意节点到其每个叶子结点的所有路径都包含相同数目的黑色结点
5.红色结点的父结点和子结点都是黑色结点

红黑树特性推论

1.如果一个结点只有一个孩子，那么该结点的颜色一定是黑色的，且该结点的孩子一定是红色的，如果其是红色或者其孩子是黑色，违反了第4条特性
2.如果一个结点没有孩子，那么该结点可能是黑色，也可能是红色
3.如果一个黑色结点有孩子，在只有一个孩子的情况下，该孩子一定是红色，如果有两个孩子，那么孩子可能是都是黑色，也可能是都是红色，也有可能是一红一黑
4.如果一个黑色结点没有孩子，如果这个结点不是根节点，那么这个结点一定有兄弟，如果该结点的父结点是红色，那么兄弟可能是黑色，也可能是红色，如果该结点的父结点是黑色，那么兄弟结点一定是黑色

红黑树的插入

为了方便插入之后调整，插入时如下：
1.如果结点是空，即是根节点，则直接分配内存，然后进入调整
2.如果插入值大于该结点的值
1).如果该结点有右孩子，则往右边插入
2).否则为当前结点的右孩子分配内存，然后调整
3.如果插入值小于该结点的值
1).如果该结点有左孩子，则往左边插入
2).否则为当前结点的左孩子分配内存，然后调整

红黑树的插入代码

void insert(RBTNodePtr& node, _DataType value)
{
	/*如果结点是空，即是根节点，则直接分配内存，然后进入调整*/
	if (!node)
	{
		node = new RBTNode<_DataType>(value);
		insertFix(node, node->m_parent);
	}
	else
	{
		/*如果插入值大于该结点的值*/
		if (value > node->m_value)
		{
			/*如果该结点有右孩子，则往右边插入*/
			if (node->m_rightChild)
			{
				insert(node->m_rightChild, value);
			}
			/*否则为当前结点的右孩子分配内存，然后调整*/
			else
			{
				node->m_rightChild = new RBTNode<_DataType>(value, node);
				insertFix(node->m_rightChild, node);
			}
		}
		/*如果插入值小于该结点的值*/
		else
		{
			/*如果该结点有左孩子，则往左边插入*/
			if (node->m_leftChild)
			{
				insert(node->m_leftChild, value);
			}
			/*否则为当前结点的左孩子分配内存，然后调整*/
			else
			{
				node->m_leftChild = new RBTNode<_DataType>(value, node);
				insertFix(node->m_leftChild, node);
			}
		}
	}
}

红黑树的插入的情况

1.插入的结点是根结点，此时只需把结点染成黑色即可
2.插入的结点的父结点是黑色，则不需做任何调整，因为红色结点不影响黑高
3.插入的结点的父结点是红色，此时有两个连起来的红色结点，违反了红黑树的特性，因此需要对红黑树做调整

红黑树的插入调整

1.如果新插入的结点有叔叔结点，且叔叔结点的颜色是红色（父结点是红色的），则将父结点和叔叔结点都染成黑色，将祖父结点染成红色，把祖父结点当作新插入结点向上调整
2.如果新插入的结点没有叔叔结点或者叔叔结点时黑色，则：
1).如果父结点是祖父结点的左孩子且新插入的结点是父结点的左孩子，则将父结点染成黑色，将祖父结点染成红色，对祖父结点进行右旋（LL）
2).如果父结点是祖父结点的右孩子且新插入的结点是父结点的右孩子，则将父结点染成黑色，将祖父结点染成红色，对祖父结点进行左旋（RR）
3).如果父结点是祖父结点的左孩子且新插入的结点时父结点的右孩子，则将新插入的结点染成黑色，将祖父结点染成红色，对父结点进行左旋，然后对祖父结点进行右旋（LR）
4).如果父结点是祖父结点的右孩子且新插入的结点时父结点的左孩子，则将新插入的结点染成黑色，将祖父结点染成红色，对父结点进行右旋，然后对祖父结点进行左旋（RL）

红黑树的插入调整代码

就按照上面的过程写就可以了。

void insertFix(RBTNodePtr node, RBTNodePtr nodeParent)
{
	/*插入的结点是根结点，此时只需把结点染成黑色即可*/
	if (!nodeParent)
	{
		node->m_color = Color::BLACK;
		return;
	}
	/*插入的结点的父结点是黑色，则不需做任何调整，因为红色结点不影响黑高*/
	else if (nodeParent->m_color == Color::BLACK)
	{
		return;
	}
	/*插入的结点的父结点是红色，此时有两个连起来的红色结点，违反了红黑树的特性，因此需要对红黑树做调整*/
	else
	{
		RBTNodePtr nodeGrandFather = nodeParent->m_parent;
		RBTNodePtr nodeUncle = (nodeParent == nodeGrandFather->m_leftChild) ? 
			nodeGrandFather->m_rightChild : 
			nodeGrandFather->m_leftChild;
		/*如果新插入的结点有叔叔结点，且叔叔结点的颜色是红色（父结点是红色的），则将父结点和叔叔结点都染成黑色，
		将祖父结点染成红色，把祖父结点当作新插入结点向上调整*/
		if (nodeUncle && nodeUncle->m_color == Color::RED)
		{
			nodeUncle->m_color = Color::BLACK;
			nodeParent->m_color = Color::BLACK;
			nodeGrandFather->m_color = Color::RED;
			insertFix(nodeGrandFather, nodeGrandFather->m_parent);
		}
		/*如果新插入的结点没有叔叔结点或者叔叔结点时黑色*/
		else
		{
			/*如果父结点是祖父结点的左孩子且新插入的结点是父结点的左孩子，则将父结点染成黑色，
			将祖父结点染成红色,对祖父结点进行右旋（LL）*/
			if (nodeParent == nodeGrandFather->m_leftChild && node == nodeParent->m_leftChild)
			{
				nodeParent->m_color = Color::BLACK;
				nodeGrandFather->m_color = Color::RED;
				rightRotate(nodeGrandFather);
			}
			/*如果父结点是祖父结点的右孩子且新插入的结点是父结点的右孩子，则将父结点染成黑色，
			将祖父结点染成红色,对祖父结点进行左旋（RR）*/
			else if (nodeParent == nodeGrandFather->m_rightChild && node == nodeParent->m_rightChild)
			{
				nodeParent->m_color = Color::BLACK;
				nodeGrandFather->m_color = Color::RED;
				leftRotate(nodeGrandFather);
			}
			/*如果父结点是祖父结点的左孩子且新插入的结点时父结点的右孩子，则将新插入的结点染成黑色，
			将祖父结点染成红色，对父结点进行左旋，然后对祖父结点进行右旋（LR）*/
			else if (nodeParent == nodeGrandFather->m_leftChild && node == nodeParent->m_rightChild)
			{
				node->m_color = Color::BLACK;
				nodeGrandFather->m_color = Color::RED;
				leftRotate(nodeParent);
				rightRotate(nodeGrandFather);
			}
			/*如果父结点是祖父结点的右孩子且新插入的结点时父结点的左孩子，则将新插入的结点染成黑色，
			将祖父结点染成红色，对父结点进行右旋，然后对祖父结点进行左旋（RL）*/
			else
			{
				node->m_color = Color::BLACK;
				nodeGrandFather->m_color = Color::RED;
				rightRotate(nodeParent);
				leftRotate(nodeGrandFather);
			}
		}
	}
}