一、红黑树简介
红黑树（R-B Tree）,全称Red-Black Tree。它是一种自平衡二叉查找树，是计算机科学中一种非常重要的数据结构。红黑树实现比较复杂，但是它具有高效，稳定的查找效率，所以在很多地方都有应用。在C++ STL中，set, multiset, map, multimap底层都是基于红黑树实现的。
（1）红黑树性质
红黑树是一种普通的二叉树查找上，仅仅只是对每个节点添加一个颜色属性形成的，它具有以下五条性质：
节点是红色或黑色。
根节点是黑色。
每个叶子节点（NIL节点，空节点）都是黑色的。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
二、红黑树的基本操作
（1）左旋操作
左旋操作是用来修正红结点出现在右边的情况。操作主要步骤：
x的右孩子变成y的左孩子
y的左孩子变成x
y作为新的子链返回
void _Rb_tree_rotate_left(_Rb_tree_node_base* node_x, _Rb_tree_node_base*& __root)
{
//获取y节点
_Rb_tree_node_base* node_y = node_x->_M_right;
//1. x节点的右孩子变成y的左孩子，同时修正y节点左孩子的父节点指针
node_x->_M_right = node_y->_M_left;
if (node_y->_M_left != 0)
{
node_y->_M_left->_M_parent = node_x;
}
//2. 修正y的父节点指针，然后将y作为子链返回
node_y->_M_parent = node_x->_M_parent;
if (node_x == __root)
{
//如果x节点根节点，则使用新的y子链更新根节点
__root = node_y;
}
else if (node_x == node_x->_M_parent->_M_left)
{
//如果x节点是左节点，则使用新的y子链更新
node_x->_M_parent->_M_left = node_y;
}
else
{
//如果x节点是右节点，则使用新的y子链更新
node_x->_M_parent->_M_right = node_y;
}
//3. 将y的左孩子变成x，同时修正x的父节点指针
node_y->_M_left = node_x;
node_x->_M_parent = node_y;
}（2）右旋操作
x的左孩子变成y的右孩子
y的右孩子变成x
y作为新的子链返回
void _Rb_tree_rotate_right(_Rb_tree_node_base* node_x, _Rb_tree_node_base*& __root)
{
//获取y节点
_Rb_tree_node_base* node_y = node_x->_M_left;
//1. x节点的左孩子变成y的右孩子，同时修正y节点右孩子的父节点指针
node_x->_M_left = node_y->_M_right;
if (node_y->_M_right != 0)
{
node_y->_M_right->_M_parent = node_x;
}
//2. 修正y的父节点指针，然后将y作为子链返回
node_y->_M_parent = node_x->_M_parent;
if (node_x == __root)
{
//如果x节点根节点，则使用新的y子链更新根节点
__root = node_y;
}
else if (node_x == node_x->_M_parent->_M_right)
{
//如果x节点是右节点，则使用新的y子链更新
node_x->_M_parent->_M_right = node_y;
}
else
{
//如果x节点是左节点，则使用新的y子链更新
node_x->_M_parent->_M_left = node_y;
}
//3. 将y的右孩子变成x，同时修正x的父节点指针
node_y->_M_right = node_x;
node_x->_M_parent = node_y;
}三、红黑树的插入操作
（1）将红黑树当作一颗二叉查找树，将节点插入
（2）将插入的节点着色为红色
（3）通过一系列旋转或着色等操作，使之重新成为一颗红黑树
| 一级分类 | 二级分类 | 三级分类 | 处理策略 | |
|---|---|---|---|---|
| case 1 | x是根节点 | (1) 根节点设为黑色 | ||
| case 2 | x的父节点是黑色 | |||
| case 3 | x的父节点是红色 | x的父节点是左孩子，叔节点是红色 | (1) x的父节点和叔节点设为黑色 (2) x祖父节点设为红色 (3) x的祖父节点作为新节点（即x节点），循环对x节点执行上述操作 | |
| case 4 | x的父节点是右孩子，叔节点是红色 | |||
| case 5 | x的父节点是左孩子，叔节点是黑色 | x是左孩子 | (1) x的父节点设为黑色、叔父节点设为红色 (2) 以x的祖父节点进行右旋 | |
| case 6 | x是右孩子 | (1) x的父节点作为新的节点（即x节点） (2) 以x节点进行左旋 (3) 再按照x是左孩子情况继续处理 | ||
| case 7 | x的父节点是右孩子，叔节点是黑色 | x是左孩子 | (1) x的父节点作为新的节点（即x节点） (2) 以x节点进行右旋 (3) 再按照x是右孩子情况继续处理 | |
| case 8 | x是右孩子 | (1)x的父节点设为黑色、叔父节点设为红色 (2)以x的祖父节点进行左旋 |
//用于插入新节点后重新形成红黑树，node_x为指向新增节点的指针，__root为指向根节点的指针
void _Rb_tree_rebalance(_Rb_tree_node_base* node_x, _Rb_tree_node_base*& __root)
{
//将新插入的节点涂成红色
node_x->_M_color = _S_rb_tree_red;
//1. （如果x是根节点），或（x的父节点是黑色），则不进入循环，将根节点涂黑即可。
//2. （如果x是非根节点，并且父节点是红色），则进入循环，调整树使之满足红黑树性质。
while (node_x != __root && node_x->_M_parent->_M_color == _S_rb_tree_red)
{
//x节点的父节点是左节点
if (node_x->_M_parent == node_x->_M_parent->_M_parent->_M_left)
{
// 取出x节点的叔节点
_Rb_tree_node_base* node_y = node_x->_M_parent->_M_parent->_M_right;
//如果叔节点是红色
if (node_y && node_y->_M_color == _S_rb_tree_red)
{
node_x->_M_parent->_M_color = _S_rb_tree_black;
node_y->_M_color = _S_rb_tree_black;
node_x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
//将祖父节点设为当前节点；继续对当前节点进行操作
node_x = node_x->_M_parent->_M_parent;
}
else
{
//叔节点是空或黑色（按规定，空节点也是黑色），且x节点是父节点的右孩子
if (node_x == node_x->_M_parent->_M_right)
{
//将x的父节点作为新节点，并以新节点为支点进行左旋
node_x = node_x->_M_parent;
_Rb_tree_rotate_left(node_x, __root);
}
//将父节点设为黑色
node_x->_M_parent->_M_color = _S_rb_tree_black;
//将祖父节点设为红色
node_x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
// 以祖父节点为支点进行右旋
_Rb_tree_rotate_right(node_x->_M_parent->_M_parent, __root);
}
}
else //x节点的父节点是右节点
{
// 取出x节点的叔节点
_Rb_tree_node_base* node_y = node_x->_M_parent->_M_parent->_M_left;
//如果叔节点是红色
if (node_y && node_y->_M_color == _S_rb_tree_red)
{
node_x->_M_parent->_M_color = _S_rb_tree_black;
node_y->_M_color = _S_rb_tree_black;
node_x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
//将祖父节点设为当前节点；继续对当前节点进行操作
node_x = node_x->_M_parent->_M_parent;
}
else
{
//叔节点是空或黑色（按规定，空节点也是黑色），且x节点是父节点的左孩子
if (node_x == node_x->_M_parent->_M_left)
{
//将x的父节点作为新节点，并以新节点为支点进行右旋
node_x = node_x->_M_parent;
_Rb_tree_rotate_right(node_x, __root);
}
//将父节点设为黑色
node_x->_M_parent->_M_color = _S_rb_tree_black;
//将祖父节点设为红色
node_x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
//以祖父节点为支点进行左旋
_Rb_tree_rotate_left(node_x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _S_rb_tree_black;
}四、红黑树的删除操作
（1）将红黑树当作一颗二叉查找树，将节点删除。
（2）通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
//用于删除节点后调整树形, __z为待删除点,__root为根节点,__leftmost左极点，__rightmost为右极点
_Rb_tree_node_base* _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
//暂存要删除的节点
_Rb_tree_node_base* node_y = __z;
_Rb_tree_node_base* node_x = 0;
_Rb_tree_node_base* node_x_parent = 0;
if (node_y->_M_left == 0)
{
node_x = node_y->_M_right; // node_x might be null.
}
else
{
if (node_y->_M_right == 0)
{
node_x = node_y->_M_left; // node_x is not null.
}
else
{
// __z的左右子树非空
//寻找y（即z）的右子树中，值最小的节点
node_y = node_y->_M_right; // __z's successor. node_x might be null.
while (node_y->_M_left != 0)
{
node_y = node_y->_M_left;
}
//取最小的节点的右节点
node_x = node_y->_M_right;
}
}
if (node_y != __z)
{
//case: 针对__z左右子非空的删除操作。
__z->_M_left->_M_parent = node_y;
node_y->_M_left = __z->_M_left;
if (node_y != __z->_M_right)
{
node_x_parent = node_y->_M_parent;//记录(替换__z的节点)的父节点
if (node_x)
{
node_x->_M_parent = node_y->_M_parent;
}
node_y->_M_parent->_M_left = node_x; // __y must be a child of _M_left
node_y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = node_y;
}
else
{
node_x_parent = node_y; //记录(替换__z的节点)的父节点
}
//删除__z节点
if (__root == __z)
{
__root = node_y;
}
else if (__z->_M_parent->_M_left == __z)
{
__z->_M_parent->_M_left = node_y;
}
else
{
__z->_M_parent->_M_right = node_y;
}
node_y->_M_parent = __z->_M_parent;
//维持颜色不变
std_swap(node_y->_M_color, __z->_M_color);
node_y = __z; //指向实际需要删除的节点
}
else
{
//case: 针对__z至少存在一个空子节点的删除操作。
//取出y（即z节点）的父节点，
node_x_parent = node_y->_M_parent;
//更新x的父节点
if (node_x)
{
node_x->_M_parent = node_y->_M_parent;
}
if (__root == __z)
{
__root = node_x;
}
else
{
//如果z是左节点，直接删除z节点
if (__z->_M_parent->_M_left == __z)
{
__z->_M_parent->_M_left = node_x;
}
else //如果z是右节点，直接删除z节点
{
__z->_M_parent->_M_right = node_x;
}
}
//更新左极值点，stl附加功能，非红黑树必须操作
if (__leftmost == __z)
{
if (__z->_M_right == 0) // __z->_M_left must be null also
{
__leftmost = __z->_M_parent;
// makes __leftmost == _M_header if __z == __root
}
else
{
__leftmost = _Rb_tree_node_base::_S_minimum(node_x);
}
}
//更新右极值点，stl附加功能，非红黑树必须操作
if (__rightmost == __z)
{
if (__z->_M_left == 0) // __z->_M_right must be null also
{
__rightmost = __z->_M_parent;
// makes __rightmost == _M_header if __z == __root
}
else // node_x == __z->_M_left
{
__rightmost = _Rb_tree_node_base::_S_maximum(node_x);
}
}
}
//删除的是红节点，无需处理。所以这里只针对node_y是非红节点进行处理。
if (node_y->_M_color != _S_rb_tree_red)
{
while (node_x != __root && (node_x == 0 || node_x->_M_color == _S_rb_tree_black))
{
if (node_x == node_x_parent->_M_left)
{
//case: node_x是左节点
_Rb_tree_node_base* node_w = node_x_parent->_M_right;
if (node_w->_M_color == _S_rb_tree_red)
{
node_w->_M_color = _S_rb_tree_black;
node_x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(node_x_parent, __root);
node_w = node_x_parent->_M_right;
}
if ((node_w->_M_left == 0 || node_w->_M_left->_M_color == _S_rb_tree_black) &&
(node_w->_M_right == 0 || node_w->_M_right->_M_color == _S_rb_tree_black))
{
node_w->_M_color = _S_rb_tree_red;
node_x = node_x_parent;
node_x_parent = node_x_parent->_M_parent;
}
else
{
if (node_w->_M_right == 0 || node_w->_M_right->_M_color == _S_rb_tree_black)
{
if (node_w->_M_left)
{
node_w->_M_left->_M_color = _S_rb_tree_black;
}
node_w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(node_w, __root);
node_w = node_x_parent->_M_right;
}
node_w->_M_color = node_x_parent->_M_color;
node_x_parent->_M_color = _S_rb_tree_black;
if (node_w->_M_right)
{
node_w->_M_right->_M_color = _S_rb_tree_black;
}
_Rb_tree_rotate_left(node_x_parent, __root);
break;
}
}
else
{
//case: node_x是右节点
_Rb_tree_node_base* node_w = node_x_parent->_M_left;
if (node_w->_M_color == _S_rb_tree_red)
{
node_w->_M_color = _S_rb_tree_black;
node_x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(node_x_parent, __root);
node_w = node_x_parent->_M_left;
}
if ((node_w->_M_right == 0 || node_w->_M_right->_M_color == _S_rb_tree_black) &&
(node_w->_M_left == 0 || node_w->_M_left->_M_color == _S_rb_tree_black))
{
node_w->_M_color = _S_rb_tree_red;
node_x = node_x_parent;
node_x_parent = node_x_parent->_M_parent;
}
else
{
if (node_w->_M_left == 0 || node_w->_M_left->_M_color == _S_rb_tree_black)
{
if (node_w->_M_right)
{
node_w->_M_right->_M_color = _S_rb_tree_black;
}
node_w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(node_w, __root);
node_w = node_x_parent->_M_left;
}
node_w->_M_color = node_x_parent->_M_color;
node_x_parent->_M_color = _S_rb_tree_black;
if (node_w->_M_left)
{
node_w->_M_left->_M_color = _S_rb_tree_black;
}
_Rb_tree_rotate_right(node_x_parent, __root);
break;
}
}
}
if (node_x)
{
node_x->_M_color = _S_rb_tree_black;
}
}
return node_y;
}