一、红黑树概念
红黑树，是一种二叉搜索树，但在每一个节点上增加了一个存储位用来表示节点的颜色，可以是Red或者Black，通过对任何一条从根到叶子的路径上各结点着色方式颜色的，确保了没有任何一条路径会比其它路径长出两倍，因此是接近平衡的。
二、红黑树性质
1、根节点是黑色。
2、每个节点不是黑色就是红色
3、对于每一个节点来说，从该节点到其后代所有叶子节点的路径上，黑色节点数量相同。
4、如果一个节点是红色的，则它的两个孩子必定是黑色节点。(不能存在连续红节点)
5、每个叶子节点都是黑色的(此处的叶子结点指的是空节点)
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点
个数的两倍？
三、红黑树节点定义
enum colour //颜色
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K,V>* _parent; //节点双亲
RBTreeNode<K,V>* _left; //节点左孩子
RBTreeNode<K,V>* _right; //节点右孩子
pair<K,V> _data; //建值对
colour _col; //枚举来存颜色
//构造函数
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) //节点默认给红色
{}
};
四、红黑树插入
红黑树是在二叉搜索树的基础上加了一些条件，因此红黑树的插入分两步：
1、按照二叉搜索树的规则插入新节点
2、根据红黑树规则变色或翻转
情况1：uncle存在且颜色为红 ： 变色
21是新增节点，我们节点构造的时候颜色默认给的是红色，因此插入的时候颜色肯定是不符合红黑树规则的，那么我们肯定需要调整，我们能不能直接把21变黑呢？肯定是不可以的，这违反了红黑树任意一条路径黑色节点个数相同的规定。那么我们只能向上调整了。
我们来看 21的parent(22)和uncle(27)，我们发现parent和uncle的颜色都是红色，那么我们只需要把parent和uncle的颜色变为黑色，然后把grandfather(25)的颜色变成黑色就可以保证路径黑色节点数量相同。看上面的图，如果我们这样做之后还是有连续的红色结点，这个时候我们需要继续向上调整，让cur = grandfater，parent = cur->_parent，循环往上走。这个时候uncle(8)也是红色，那么把uncle和parent都变为黑色，让grandfather(13)变为红色即可。这个时候还要继续循环往上走，这个时候cur是13，也就是根结点，它的parent不存在，循环也就结束了。因此循环的条件parent存在且parent->col==Red。循环结束后根结点是红色，我们把根节点颜色变成黑色。这样就结束了。
情况2：uncle不存在或uncle颜色为黑 ：旋转
（1）左旋
左旋条件：uncle为黑或者uncle不存在，并且parent为grandfather右边，cur为parent右边。
旋转完成后将parent变为黑色，然后将grandfather颜色变为红色。
如果uncle为黑或者uncle不存在呢？看下面的图一。
21是新增节点，当我们调整到cur为25的时候，uncle为8，它是个黑色节点，这个时候应该如何呢？我们看这颗树就会发现它已经失衡了，因为它最长路径中节点个数超过最短路径节点个数的两倍了，因此我们需要用到AVL树时候玩的旋转。我们看这颗树，它明显是右边高，以grandfather为旋转点进行左旋看看会发生什么。左旋之后它果然平衡了。
（2） 右左双旋
右左双旋条件：uncle为黑或者uncle不存在，并且parent为grandfather右边，cur为parent左边。
旋转完成后将cur颜色变为红色，grandfather颜色变为红色。
13为新增节点
（3）右旋
右旋条件：uncle为黑或者uncle不存在，而且parent在grandfather的左边并且cur在parent的左边时。
旋转完成后将parent的颜色变为黑色，grandfather的颜色变为红色。
7为新增节点
（4）左右双旋
左右双旋条件：uncle为黑或者uncle不存在，而且parent在grandfather的左边并且cur在parent的右边时。
旋转完成后将cur颜色变为红色，grandfather颜色变为红色。
9为新增节点
总结：
这里其实就分为两种情况：
第一种情况parent在grandfather左边。在这种情况下如果uncle存在且为红，进行变色。如果uncle不存在或者为黑，进行旋转，如果cur在parent左边就进行右旋，如果cur在parent右边就进行左右双旋。旋转之后直接break跳出循环。
第二种情况parent在grandfather右边。在这种情况下如果uncle存在且为红，进行变色。如果uncle不存在或者为黑，进行旋转，如果cur在parent右边就进行左旋，如果cur在parent左边就进行右左双旋。旋转之后直接break跳出循环。
单旋之后一律将parent变为黑色，grandfather颜色变为红色。
双旋之后一律将cu变为红色，grandfather颜色变为红色。
在最后将根节点颜色变为黑色。
插入代码：
bool Insert(const pair<K,V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else //相等直接return false
{
return false;
}
}
cur = new Node(kv);
cur->_col = RED;
Node* newnode = cur;//这里提前保存一下cur，因为红黑树翻转可能导致cur改变
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if ( parent == grandfather->_left )//1111
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) //uncle存在且为红
{
parent->_col = uncle->_col = BLACK;//变色
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或存在且为黑
{
//右
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
//左右
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
//左
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
//右左
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
五、判断是否为红黑树
我们可以先判断树的根节点是否为黑色，然后去判断每一条路径的黑色节点个数是否相等，在判断是否有连续红色节点。
bool IsBRTree()
{
return IsBRTree(_root);
}
bool IsBRTree(Node* root)
{
if (root == nullptr)//空树也是红黑树
return true;
if (root->_col != BLACK)//判断根节点是否为黑色
{
return false;
}
int basevale = 0;
Node* cur = root;
while (cur) //先去最左边路径，统计黑色节点个数
{
if (cur->_col == BLACK)
{
basevale++;
}
cur = cur->_left;
}
return CheackColour(root, 0, basevale);
}
bool CheackColour(Node* root, int blacknum, int baseval)
{
if (root == nullptr)//说明一条路径走完了
{
if (blacknum != baseval)//判断每条路径黑色节点个数是否相同
return false;
return true;
}
if (root->_col == BLACK)//统计该路径黑色节点个数
{
++blacknum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)//判断是否有
//连续红色节点
{
cout << "出现连续红色结点" << endl;
return false;
}
return CheackColour(root->_left, blacknum, baseval)
&& CheackColour(root->_right, blacknum, baseval);
}
