_Rb_tree_rotate_left 函数的功能是以节点 __x 和其右孩子 __y 为支轴进行左旋，左旋之后节点 __y 上升成为父节点，而 __x 下降成为 __y 的左孩子， __y 原先的左孩子成为 __x 的右孩子。同时如果原先 __x 为根节点，则旋转之后 __y 成为新的根节点。
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_right;
__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y;
__y->_M_left = __x;
__x->_M_parent = __y;
}
函数 _Rb_tree_rotate_right 功能是以节点 __x 和其左孩子 __y 为支轴进行右旋，旋转之后节点 __y 上升成为父节点。__x 下降成为 __y 的右孩子，__y 原先的右孩子成为 __x 的左孩子。如果 __x 原来是根节点，那么 __y 成为新的根节点。
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_left;
__x->_M_left = __y->_M_right;
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y;
__y->_M_right = __x;
__x->_M_parent = __y;
}
stl_tree.h 中对红黑树的插入和删除节点之后，为维护红黑树的性质采取的调整策略是依照算法导论上的叙述而来的。
依照算法导论上的叙述，红黑树一共有五条性质。
- (1) 红黑树的每个节点或者是红的，或者是黑的。
- (2) 红黑树的根节点是黑的。
- (3) 红黑树的每个叶节点是黑的。
- (4) 如果红黑树的一个节点是红的，那么他的两个儿子节点都是黑的。
- (5) 对于红黑树的每个节点，从该节点到其任何一个为叶节点的子孙节点的路径上所包含的黑节点数目是相同的。
函数 _Rb_tree_rebalance 用来在插入一个新节点 __x 之后，为维护红黑树的性质，对红黑树进行调整。函数中首先将节点 __x 的颜色值置为红色，和算法导论上讨论的一样，初始时节点 __x 有两个颜色值为黑色的儿子节点，这俩个儿子节点为空节点，而且被作为红黑树的叶节点。
while 循环中要求 __x 不为根节点，同时要求 __x 的父节点的颜色不为黑色。因为如果 __x 为根节点，则简单的将 __x 的颜色置为黑色即可。而如果 __x 的父节点的颜色为黑色，则红黑树的性质是保持的(循环从开始到结束，唯一可能违反红黑树性质的地方都是 __x 和其父节点之间)，也可以直接退出循环。
如果节点 __x 既不为根节点，而且 __x 的父节点的颜色值为红色。则分两种情况进行讨论，这两种情况是对称的，弄明了其中一种，另一种也就不言自明。
情况 1 ，如果 __x 的父节点是 __x 的父节点的父节点的左孩子(从第一个 if 语句进入情况 1)。则令 __y 是 __x 的父节点的父节点的右孩子(即 __x 的叔叔，__x 的父节点的兄弟节点)。
情况 1.1 如果节点 __y 的颜色值和 __x 的父节点的颜色值一样也为红色(第二个if 语句进入情况 1.1)，则将 __x 的父节点的颜色值和 __y 的颜色值都置为黑色，将 __x 的父节点的父节点的颜色值置为红色(__x 的父节点的父节点原先的颜色值为黑色，因为 __x 的父节点的颜色值为红色)。然后将 __x 更新为其父节点的父节点，并进入下一次循环。
情况 1.2 如果节点 __y 的颜色值和 __x 的父节点的颜色值不一样，为黑色。且 __x 为其父节点的右孩子(第一个 else 语句中的 if 语句进入情况 1.2)，则将 __x 更新为 __x 的父节点(更新之后 __x 和其右子节点的颜色值都为红色，因为更新之前 __x 和其父节点的颜色都为红色)。再对 __x 和其右子节点进行左旋。左旋之后 __x 变成了其父节点的左孩子，并且 __x 和其父节点，颜色值还都为红色。除了红黑树的第 (4) 条性质被破坏之外，其他性质都和旋转之前一样得以保持。此时进入情况 1.3
情况 1.3 如果节点 __y 的颜色值和 __x 的父节点的颜色值不一样，为黑色，且 __x 为其父节点的左孩子。则将 __x 的父节点的颜色值由红变为黑色，将 __x 的父节点的父节点的颜色值由黑色变为红色。并对 __x 的父节点的父节点进行右旋。旋转之后 __x 的父节点上升一层，且颜色值为黑色，原先 __x 的父节点的父节点下降一层，变成 __x 的父节点的右孩子，颜色值为红色。旋转之后红黑树的性质调整完毕，在进入下一次循环之后会退出整个循环。
对应的情况 2 如果 __x 的父节点为 __x 的父节点的父节点的右孩子，也可以类似调整，不再赘述。
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
__x->_M_color = _S_rb_tree_red;
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
if (__y && __y->_M_color == _S_rb_tree_red) {
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else {
if (__x == __x->_M_parent->_M_right) {
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
}
}
else {
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
if (__y && __y->_M_color == _S_rb_tree_red) {
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else {
if (__x == __x->_M_parent->_M_left) {
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _S_rb_tree_black;
}
函数 _Rb_tree_rebalance_for_erase 先按照普通二叉查找树的方法将给定的节点 __z 删除，如果因为给定节点的删除导致红黑树的性质被破坏，则对节点进行调整。
####一、节点删除部分####
首先定义了三个 _Rb_tree_node_base 类型的指针。其中 __y 和 __z (__z 为待删除节点)指向同一节点 。 __x 和 __x_parent 被初始化为空指针(__x_parent 用来记录删除过程中 __x 的父节点，在节点的调整部分需要用到，之所以不直接用 __x->_M_parent 来索引，是因为 __x 可能为空指针，但 __x 为空指针时，还是将其看成一个空节点，其还是有父节点)。
判断 __y 指向的节点是否有两个儿子节点，如果有两个儿子节点，则让 __y 指向 节点 __z 的后继节点。否则让 __x 指向节点 __y 非空的儿子节点(如果 __y 没有儿子节点，则 __x 为空指针) 。
情况 1 , 如果 __y 和 __z 不等，说明 __y 是 __z 的后继节点(此时 __x 应该为 __y 的右孩子)。则重新修改链接关系，用 __y 来代替 __z 的位置(也可以直接将 __y 删除，然后再将 __y 中的关键字拷贝到 __z 中，这是比较通用的做法。而当前函数是直接修改 _M_parent, _M_left, _M_right 的链接关系，用 __y 来替换 __z 的位置。这样做的好处是省去了数据的拷贝，但实现要略微复杂一点) 。
首先 __z 的左孩子的 _M_parent 要指向 __y ，使得 __z 原先的左孩子现在成为 __y 的左孩子(__y 原来是没有左孩子的，否则它不为 __z 的后继节点) 。
情况 1.1 如果 __y 不为 __z 的右孩子(当 __z 的右孩子没有左孩子时，__z 的右孩子为其后继节点) 。 __x 作为 __y 的右孩子应该代替原先 __y 的位置(__x 可能为空)。
__x 的 _M_parent 指向 __y 的父节点，同时更新 __x_parent 为 __y->_M_parent。__y 的父节点的 _M_left 指向 __x(如果 __y 不为 __z 的右孩子，可以肯定 __y 肯定为其父节点的左孩子，因为 __y 和其父节点的值都比 __z 要大，但如果 __y 为其父节点的右孩子，那么它的值要比其父节点大，这与 __y 是 __z 的后继节点矛盾) 。
同时 __y 的 _M_right 指向 __z 的右孩子(__y 原先的右孩子为 __x，但现在 __x 的 _M_parent 已经指向 __y 的父节点，__y 的父节点的 _M_left 也指向了 __x，__y 和 __x 已解除父子关系)， __z 的右孩子 _M_parent 指向 __y。
情况 1.2 当 __y 为 __z 的右孩子时，情况 1.1 中所作的调整都不需要，__x 和 __y 还是保持原有的父子关系即可。更新 __x_parent 为 __y。
然后根据 __z 是其父节点的左孩子还是右孩子，来设定 __y 是 __z 的父节点的左孩子还是右孩子。同时 __y 的 _M_parent 指向 __z 的父节点。并交换节点 __y 和 __z 的颜色值，至此 __y 完全替代原先 __z 的位置(函数中至始至终没有修改 __z 的链接关系，只是修改了颜色值，通过 __z 依然可以获取到其原先的父节点和孩子节点)。最后将 __z 赋值给 __y，让 __y 指向被删除的节点。
情况 2 ，如果 __y == __z 则说明 __z 至多只有一个孩子节点，指针 __x 指向这个孩子节点(如果 __y 没有孩子节点 __x 为空指针) 。首先更新 __x_parent 为 __y 的父节点。如果 __x 非空，让 __x 的 _M_parent 指向 __y 的父节点。
如果原先 __z 为根节点，则此时 __x 为根结点。 如果 __z 不为根节点且 __z 为其父节点的左孩子，则此时 __x 为 __z 的父节点的左孩子，如果 __z 不为根节点且 __z 为其父节点的右孩子则 __x 为 __z 的父节点的右孩子。
如果 __z 为最左节点，则查看其是否有右孩子(__z 已经是最左节点了，它最多只可能有右孩子，如果有右孩子，则为 __x)。如果没有，则节点 __z 既没有左孩子也没有右孩子，节点 __z 作为其父节点的左孩子(__z 是最左节点，肯定是左孩子) 被删除之后，其父节点则为最左节点。如果 __z 有右孩子，在 __z 被删除后，以其右孩子为根的子树中的最左节点即为整棵树的最左节点(通过 _Rb_tree_node_base::_S_minimum(__x) 可以求得，其中 __x 为右孩子)。
如果 __z 为最右节点，则查看 __z 是否有左孩子，如果没有，则在 __z 被删除后，其父节点成为最右节点。如果有，则以其左孩子为根的子树中的最右节点为新的最后节点(通过 _Rb_tree_node_base::_S_maximum(__x)可以求得，其中 __x 为左孩子)。
最后 __y 是指向被删除的节点。
####红黑树的调整部分####
如果节点 __y 被删除，可能破坏的红黑树性质有三种，如果 __y 为根节点，而其子节点为红色，则子节点 __x 成为新的根节点会破坏性质 (1)。同时如果 __y 原先的父节点和子节点都为红色，则删除 __y 后会破坏性质 (4)。如果 __y 的颜色值为黑色，还会破坏性质 (5)，
如果删除节点 __y 之后。不满足性质 (5) 的节点是从 __x 到根节点的路径上的所有节点，因为 __x 原先的父节点 __y 被移除了，取而代之， __y 原先的父节点变成了 __x 的父节点(唯一的一个例外是 __y 是 __z 的后继，且 __y 是 __z 的右孩子，这种情况下， __x 的父节点并没有发生改变，但不满足性质 (5) 的节点仍然是从 __x 到根节点的路径上的所有节点)。
如果被删除的节点的颜色值为黑色，为了使得从 __x 到根节点的路径上的节点满足性质 (5) ，依照算法导论上面的想法，可以先在节点 __x 多加一重黑色。然后应用旋转操作，将这额外的一重黑色不断上移，直到这重额外的黑色被加到根节点或者一个红色节点。遇到根节点，则直接拿掉这重额外的黑色仍可保持红黑树的性质。而如果遇到红色节点则将该红色节点变成黑色即可，这样可以同时维护可能被破坏的性质 (1), (4), (5) 。
while 循环的条件要求 __x 不为根节点，且要求 __x 要么为空(依照算法导论的叙述，认为空节点为叶节点，这里 __x 为空，是因为原先被删除的节点 __y 没有孩子节点，或者说只有空节点为其孩子节点。同时认为空节点的颜色值为黑色), 要么 __x 的颜色值为黑色。如果 while 循环满足条件，则分两种情况进行讨论，这两种情况彼此对称。
情况 1 。如果 __x 节点为其父节点的左孩子 (这里用 _x_parent 代替 __x->parent 是因为 __x 可能为空。而如果 __x 为空，也会进入这一种情况) 。
情况 1.1。令 __w 为 __x 的父节点的右孩子，即 __x 的兄弟节点(__w 节点肯定不为空节点，因为在删除之前 __x_parent 是有左子节点的(__x 原先的父节点)，且左子节点的颜色值为黑色，如果 __x_parent 的右子节点为空，则说明删除之前 __x_parent 到根节点路径上的节点就都是不满足性质 (5) 的，这与删除之前整棵树是红黑树矛盾)。
如果 __w 的颜色值为红色。首先可以肯定 __x 的父节点 _x_parent 的节点为黑色。然后令 __w 的颜色值为黑色，_x_parent 的颜色值为红色，以 _x_parent 和 __w 为支轴进行一次左旋，左旋之后 __w 上升成为父节点，__w 原先的左孩子成为 _x_parent 的右孩子。并且旋转之后红黑树的性质并没有发生改变，仍然是保持的。更新 __w 为 _x_parent 的右孩子。但此时 __w 的颜色值为黑色，进入情况 1.2
情况 1.2。__w 作为 _x_parent 的右孩子，且颜色值为黑色，且如果 __w 的两个孩子节点的颜色值都为黑色(如果有子节点为空节点，也认为该子节点的颜色值为黑色) 。则将 __w 的颜色值置为红色，然后将额外的一重黑色，从 __x 上升到 _x_parent。这样红黑树的性质除了可能破坏性质 (4) 之外其他的都仍然能得到保持 (如果破坏性质 (4)，说明 _x_parent 为红色节点，下一次循环时条件会得不到满足，从而退出循环。) 。如果 _x_parent 的颜色值为黑色，则就有退回到了情况 1.1。
情况 1.3。__w 作为 _x_parent 的右孩子，颜色值为黑色，且 __w 至少有一个颜色值为红色的孩子节点。但 __w 的右孩子为黑色节点(可以推测出 __w 的左孩子肯定为红色节点) ，则将 __w 的左孩子的颜色置为黑色， __w 的颜色置为红色，再以 __w 和其左孩子为支轴进行右旋，右旋之后 __w 的左孩子上升成为父节点，且颜色值为黑色，原先的 __w 节点下降成为其新父节点的右孩子。将 __w 更新为旋转之后的新父节点，对于新的 __w 节点，其右孩子颜色值为红色，此时进入情况 1.4。
情况 1.4。__w 作为 _x_parent 的右孩子，颜色值为黑色，且 __w 至少有一个颜色值为红色的孩子节点，其中 __w 的右孩子为红色节点(左孩子可能黑也可能红)。然后将 __w 的颜色值置为 __x_parent 的颜色值，将 _x_parent 的颜色值置为黑色。再将 __w 的右孩子的颜色值变成黑色，__w 的右孩子颜色值由红变黑，使得其黑高度，右边比左边大 1。然后以 _x_parent 和 __w 为支轴进行左旋，则 _x_parent 成为 __w 的左孩子，由于 _x_parent 为黑色，原先 __w 的左孩子成为 _x_parent 的右孩子，此时__w 的左边的黑高度因为 __x_parent 为黑色会增加 1。是的左右相等，而且额外的一重黑色也因为 _x_parent 的加入可以被舍弃。此时红黑树的性质都得到了保持，退出循环即可。
对于对称的情况与上面的情况类似，不再赘述。
inline _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* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
__x = __y->_M_right; // __x might be null.
else
if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
__x = __y->_M_left; // __x is not null.
else { // __z has two non-null children. Set __y to
__y = __y->_M_right; // __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z) { // relink y in place of z. y is z's successor
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right) {
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // __y must be a child of _M_left
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
__STD::swap(__y->_M_color, __z->_M_color);
__y = __z;
// __y now points to node to be actually deleted
}
else { // __y == __z
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else
if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
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(__x);
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 // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
if (__y->_M_color != _S_rb_tree_red) {
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) {
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) {
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_left(__x_parent, __root);
break;
}
} else { // same as above, with _M_right <-> _M_left.
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) &&
(__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black) {
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x) __x->_M_color = _S_rb_tree_black;
}
return __y;
}
STL 的 tree 分析（一）</br> STL 的 tree 分析（二）</br> STL 的 tree 分析（三）</br> STL 的 tree 分析（四）</br> STL 的 tree 分析（五）</br>