一、红黑树的概念
红黑树是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或者Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
二、红黑树的性质
- 每个节点不是红色就是黑色。
- 根节点是黑色的。
- 如果一个节点是红色的，则它的两个孩子节点都是黑色的（不能有连续的红色节点）。
- 对于每个节点，从该节点到其所有叶子结点的路径上，均包含数目相同黑色节点。
- 每个叶子结点都是黑色的（此处的叶子结点指的是空节点）。
三、红黑树节点的定义
enum Colour//节点的颜色
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode//红黑树节点
{
RBTreeNode<K, V>* _parent;//父指针
RBTreeNode<K, V>* _left;//左指针
RBTreeNode<K, V>* _right;//右指针
Colour _col;//颜色
pair<K, V> _kv;//键值对
RBTreeNode(const pair<K, V>& kv)//构造函数
:_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_col(RED)
,_kv(kv)
{}
};四、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1、按照二叉搜索树的规则插入新节点
bool insert(const pair<K, V>& kv)//插入
{
if (_root == nullptr)//如果树为空
{
_root = new Node(kv);//直接让根节点指向新节点
_root->_col = BLACK;//根节点为黑色
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//寻找插入位置
{
parent = cur;//记录父节点
if (cur->_kv.first < kv.first)//插入的值比当前节点大
{
cur = cur->_right;//往右走
}
else if (cur->_kv.first > kv.first)//插入的值比当前节点小
{
cur = cur->_left;//往左走
}
else//插入的值与当前节点相同
{
return false;//插入失败
}
}
//找到插入的位置了，开始插入
cur = new Node(kv);
if (parent->_kv.first < kv.first)//插入到父节点的右边
{
cur->_parent = parent;
parent->_right = cur;
}
else if (parent->_kv.first > kv.first)//插入到父节点的左边
{
cur->_parent = parent;
parent->_left = cur;
}
//调整颜色
//......
_root->_col = BLACK;//根节点的颜色一定是黑色
return true;
}2、插入新节点后，红黑树的性质可能被破坏了，此时需要调整红黑树
新节点的默认颜色是红色，因此：如果新节点的父节点是黑色，则没有违反红黑树的任何性质，不需要调整；但是当新节点的父节点是红色时，就违反了性质3不能有连续的红色节点，此时需要对红黑树分情况进行讨论。
规定：cur为新节点，p为新节点的父节点，g为新节点的祖父节点，u为新节点的叔叔节点。
（1）cur为红，p为红，g为黑，u存在且为红
此时只需要通过变色就能解决。
注意：此处看到的树，可能是一颗完整的树，也可能是一棵子树
调整完成后，此时g变成了红色，如果g有父节点并且父节点为红色，此时需要继续向上调整。
（2）cur为红，p为红，g为黑，u不存在或者存在且为黑
此时我们需要通过旋转+变色的方法来调整，调整完毕后，不需要再继续向上调整，因为我们调整后，最上面的节点是黑色，此时不论它的父节点是红色还是黑色，都不需要再继续调整了。
单旋后，cur和u不变色，p变为黑色，g变为红色。
双旋后，p和u不变色，cur变为黑色，g变为红色。
关于旋转的更详细内容，可以参考：AVL树的旋转_wx635fd1fc02a16的技术博客_51CTO博客
完整的插入代码：
bool insert(const pair<K, V>& kv)//插入
{
if (_root == nullptr)//如果树为空
{
_root = new Node(kv);//直接让根节点指向新节点
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//寻找插入位置
{
parent = cur;//记录父节点
if (cur->_kv.first < kv.first)//插入的值比当前节点大
{
cur = cur->_right;//往右走
}
else if (cur->_kv.first > kv.first)//插入的值比当前节点小
{
cur = cur->_left;//往左走
}
else//插入的值与当前节点相同
{
return false;//插入失败
}
}
//找到插入的位置了，开始插入
cur = new Node(kv);
if (parent->_kv.first < kv.first)//插入到父节点的右边
{
cur->_parent = parent;
parent->_right = cur;
}
else if (parent->_kv.first > kv.first)//插入到父节点的左边
{
cur->_parent = parent;
parent->_left = cur;
}
//调整颜色
while (parent && parent->_col == RED)
{
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;
}
else//叔叔节点为空或者叔叔节点是黑色
{
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//新插入的节点在父节点的右边
{
Node* uncle = grandfather->_left;//叔叔节点
if (uncle && uncle->_col == RED)//叔叔节点不为空并且是红色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
}
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;//旋转后就不需要继续调整，跳出循环
}
}
//继续向上调整
cur = grandfather;
parent = grandfather->_parent;
}
_root->_col = BLACK;//根节点的颜色一定是黑色
return true;
}五、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(log2N)，红黑树不追求绝对平衡，其只需要保证最长路径不超过最短路径的2倍，相对AVL树而言，降低了插入和旋转的次数，所以在经常进行增删查改的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
完结。。。。。