红黑树的插入与删除-详细整理资料.doc

红黑树的插入、删除及旋转原则
Category: Uncategorized — wuxicn @ 12:29 AM
红黑树(Red-Black Tree)的插入和删除操作很繁琐，一不小心就容易弄错，不能靠强制记忆。因此，今天总结一下红黑树插入和删除操作的推导原则，包括旋转的推导原则。

本文所有内容来自三个网页
1.
2. http://icoder.me/2009/08/25/insert-delete-in-red-black-tree/
3.
如果大家能打开上面的链接，就不用再看了，我整理得不好。。
先是比较简单的插入操作的推导原则：
1. 红黑树的插入和普通搜索二叉树(Binary Search Tree)的插入一样，只是在插入完以后，将新插入的节点标记为红色，然后从该节点开始，向上进行调整颜色。
2. 向上调整颜色进行旋转时，旋转的原则是尽量用1次或者最多2次旋转完成，并且旋转操作不能影响该层以下层次的节点，只能影响其父节点，然后将其父节点（或者叔节点、兄弟节点）作为新的要调整颜色节点，继续向上递推调整。
3. 调整完后注意检查根的颜色是否还是黑色。
删除操作的推导原则：（比较麻烦！）
1. 删除节点z时，先找到z的中根后继节点y，然后将y的数据复制给z（不包括颜色），然后将y删除。这样，删除y的时候，y最多只有一个孩子节点x，将x取代y即可，然后如果y的颜色是黑色，才需要调整颜色。若要调整颜色，从x处开始向上递推的调整颜色。
2. 从x处开始向上调整颜色时也应注意不要影响该层次以下的节点，只能影响x同层或者更高层的节点。调整完后x的父节点（或者叔节点、兄弟节点）作为新的待调节点（新的x），如果new x颜色为红色时，则不用调了，直接结束。
3. 调整是应注意通过标记各层高度（黑高度）来进行推导。
4. 结束后看x是否是红色，如果是，改成黑色。
Remarks:
1. 里面提到的高度是指黑节点个数。
2. 层次也是关于黑节点来说的。
红黑树原理详解上：
前言：
        之所以要写这篇文章，第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的，
如果不想搞懂理论，而直接看代码，那绝对是云里雾里，不知所云。第二个目的是我觉得网上虽然后不少我文章也在讲，但是我就是理解
不上有点困难，在我参考了很多文章之后，认真阅读才慢慢摸透了其中的原理，所以我想用自己的方式来表达，希望有助于各位的朋友理解。
你可以在这里获得配套源代码

红黑树由来：
        他是在1972年 由Rudolf Bayer发明的，他称之为“对称二叉B树”，它现代的名字是Leo J. Guibas和 Robert Sedgewick 于1978
年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，
插入和删除，这里的n 是树中元素的数目。

红黑树性质：
1. 每个结点或红或黑。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。
5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。

讨论的前提：
1，我们只讨论往树的左边和从树的左边删除的情况，与之对称的情况一样。
2，假设我们要删除一个元素的方法都是采取删除后继节点，而非前驱节点。
3，NL或全黑表示黑空节点，也可以不用画出。
4，“=>”这个符号我们用来表示“变成”的意思。
一． 插入
当红黑树中没有节点的时候，新节点直接涂黑就可以了。
当树中已有节点，我们就将新节点涂红，并且底下挂两个黑空节点。

1.1 新节点的父亲为黑色
这种情况最简单，只接插入将新节点可以了，不会出现红色警戒。

1.2 新节点的父亲为红色
这种情况出现红色警戒，并且通过红色的父亲，我们可以推出一定有一个黑色的父， 并且父亲不可能为树根(树根必须为黑)。

这种情况需要修复。
1.2.1 新节点的叔叔是红色。（红叔）

图1.2.1-1

图1.2.1-2

注解：在这种情况下，我们可以通过这样的方式来修复红黑树的性质。因为遇到红 色警戒所以我们首先可以想到的就是将父亲变成黑色，但这样祖父的左子树的黑高 就增加了，为了达到祖父的平衡，我们红叔变成黑色，这样祖父就平衡了。但是整 个祖父这颗树的高度增高了，所以再此将祖父的颜色变成红色来保持祖父这颗树的 高度不变。因为祖父变成了红色，因此往上遍历。
      方法：父=>黑；叔=>黑；祖=>红；往上遍历；
1.2.2 新节点的叔叔是黑色（黑叔）

图1.2.2-1

图1.2.2-2
注解：首先可以说明的是，这种情况下我们都可以通过改变颜色和旋转的方式到达 平衡，并且不再出现红色警戒，因为无需往上遍历。图1.2.2-1：首先我们将红父变 成黑色，祖父变成红色，然后对祖父进行右旋转。这样我们可以看到，整颗树的黑 高不变，并且这颗树的左右子树也达到平衡。新的树根为黑色。因此无需往上遍历。
方法：图1.2.2-1  父=>黑；祖=>红；祖父右旋转；
                图1.2.2-2   新=>黑；祖=>红；父左旋转；祖右旋转；

插入我们就算做完了，与之对称的右边插入的情况完全一样，请自己下来分析；
一． 删除
删除是比较经典但也是最困难的一件事了，所以我们必须一步一步地理解。为了中途思想不混乱，请始终记住一点，下面我们删除的节点都已经表示的是实际要删除的后继节点了。因此可以得出一下结论。
    首先，可以肯定的是我们要删除的节点要么是红色，要么是黑色。
    其次，既然我们要删除的结点是后继节点，那么要删除的节点的左子树一定为空。所以当删除的节点为黑色时只剩下两种情况。
    最后，如果删除的节点为红色，那么它必为叶子节点。(自己好好想象为什么)。
请在看下面的内容前先牢记上面的结论，这样更加方便让你理解下面的知识。
a：当删除的节点为黑色时

              删黑a               删黑b

b：当删除的节点为红色时

     上面的几附图都是很简单的。因为你可以将空节点 去掉不看。所就形成了要 删除的节点要么有一个右孩子，要么为叶子节点。

下面我们就开始真正的删除操作了。
2.1 删除红色节点

注解：这种情况是最简单的，因为根据上面的结论我们可以推出子节点     一定为空， 也就是说删除的红色节点为叶子节点。只需将这个旧节点的右孩子付给父亲的左孩子就 可以了，高度不变。
方法：略

2.2 删除黑色节点
         遇到黑色节点情况就将变得复杂起来，因此我们一定要慢慢来，仔细分析。
         2.2.1当删除的节点有一个红色子孩子

注解：这种情况其实就是上面我们分析的三种情况之一，如图"删黑b"。这种情况 是非常简单的，只需将旧节点的右孩子取代旧节点，并将子孩子的颜色变为黑色， 树平衡；
       方法：子取代旧；子=>黑；
2.2.2当删除的节点无左右孩子
这种情况其实就是上面我们分析的三种情况之一，如图"删黑a"。我们推出子节点 一定为空，请务必记住这点，不然在后面你将很容易被混淆，父亲的颜 色我们标记为绿色，是表示，父亲的颜色可为红或黑。黄色的子节点其实就 是一个黑空节点，这样方便后面分析。

a：红兄

注解：当我们删除的节点拥有一个红色的兄弟时，这种情况还相对比较简单，因为 兄弟为黑色，我们可以推出父亲一定为黑色。因为父节点的左树高度减一，所 以我们可以通过左旋转父节点，来将节点1旋转到左边来恢复左边的高度。然 后将父变成红，兄变成黑。这样整颗树的高度不变，父节点也平衡记住子节点 为空所以可以删除看，这样便于理解。其实我们也可以推出1，2为空，但这里没有必要。
      方法：父=>红；兄=>黑；左旋转父节点；

b ：黑兄
     遇到黑兄就又麻烦了，我们又必须引入要删除的节点的侄子了。所以我们这里 再次细分为b1: 黑兄 双黑侄 b2: 黑兄 左黑侄右红侄 b3: 黑兄 右黑侄左红侄。 可能你会问b4呢，双红侄的情况呢？其实双红侄的情况同属于b2,b3的情况，所以 可以默认用 b2,b3其中一种情况来处理就可以了。
现在我们开始了
     b1黑兄 双黑侄

注解：我们首先可以肯定的是父节点的左子树高度减一了，所以我们必须想方设法 来弥补这个缺陷。如果我们把父节点的右子树高度也减一（兄变成红色）那么 父节点这颗树就可以保持平衡了，但整颗树的高度减一，所以我们可以判断， 如果父亲是红色，那么我们可以通过把父亲变成黑色来弥补这一缺陷。但如果 父亲是黑色呢，既然遇到到黑色了我们就只好往上遍历了。
方法：兄=>红；子=黑；    红父=>黑;
                                 往上遍历(黑父);
补充：其实子节点就是空节点，没有必要变。就算遍历上去，父节点也为黑
b2黑兄 左黑侄右红侄

注解绿色表示，颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一，所以我们可以通过将父节点旋转下来并且变为黑色来弥补，但由于兄弟被旋转上去了，又导致右子树高度减一，但我们这有一个红侄，所以可以通过红侄变成黑色来弥补。父亲所在位置的颜色不变；(子为空)
方法：兄=>父色；父=>黑；侄=>黑；(子=>黑)；左旋转父节点；

b3 黑兄 左红侄右黑侄

注解：绿色表示，颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一,同样我们通过父节点左旋转到左子树来弥补这一缺陷。但如果直接旋转的话，我们可以推出左右子树将不平衡(黑父)，或者两个红色节点相遇(红父)；这样将会更加的复杂甚至不可行。因此，我们考虑首先将兄弟所在子树右旋转，然后再左旋转父子树。这样我们就可以得到旋转后的树。然后通过修改颜色来使其达到平衡，且高度不变。
方法：侄=>父色；父=>黑;右旋转兄；左旋转父；

总结：
如果我们通过上面的情况画出所有的分支图，我们可以得出如下结论
插入操作：解决的是 红-红 问题
删除操作：解决的是 黑-黑 问题
即你可以从分支图中看出，需要往上遍历的情况为红红(插入)；或者为黑黑黑（删除）的情况，，如果你认真分析并总结所有的情况后，并坚持下来，红黑树也就没有想象中的那么恐怖了，并且很美妙；

· 版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明

红黑树删除节点函数Rb_tree_rebalance_for_erase 详析（注，以下内容我也没找到相关的图片，大家只有自己理解了，抱歉）

       在编程时，会碰上多少让你发疯想死的代码？这样的程序代码的存在妈的简直对人的信心就是种极度挑战，而且搞懂这些代码，不会让你有任何成就感，而只会更加恨能写得出这些代码的二逼。仅仅一段代码一个函数，搞了几天才完全搞通，别说成就感了，净剩下拿刀捅人的冲动了。

       在读SGI/STL版本的STL实作的源代码时，遇上了一个罕见复杂抽象的内部全局函数_Rb_tree_rebalance_for_erase，这个函数是我所见过的为数不多的可以用“恐怖”去形容的，其恐怖到什么程度：在侯捷的《STL源代码剖析》一书中，对于红黑树的操作这节内容中，他只讲到插入节点的操作，居然对删除节点的操作只字不提，不知道是不是故意的。究其原因，不知道是不是跟这个诡异复杂的函数有些联系。

       这个函数是在红黑树删除节点之前做的准备工作，当然，删除过程中的绝大部分任务就是由这个函数完成的。从这个函数中出来之后，树还是平衡的，而实际要删除的节点已经和红黑树分离开来了，基本上剩下的只要在内存管理器中消除节点就够了。

       这万恶的函数如下：
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 )
      看该函数的原型，该函数的目的是将z节点从整个红黑树中去除（并非从内存管理器中最终删除，最终从内存管理配置器中删除该节点的任务不是由此函数完成的）并使剩下的树继续组成一个平衡的红黑树；函数最终返回指向被去除节点的迭代器。但是这函数有个大前提：函数执行前的红黑树也必须是平衡的，抛开这个前提，别的无从谈起。

      该函数完成了两个主要工作：
      1． 将z节点从整个树中去除并将其位置保存；
      2． 调整剩余红黑树节点使其重新达到平衡。
      我们一步一步来看。

1. 将z节点从整个树中去除
       第一步，我们不考虑红黑树平衡性，仅是单纯从树中去除z节点。这需要在函数中定义一个局部迭代器y并最终将z保存到y中，函数最后只需返回y即可。
删除二叉搜索树中任意节点的原则其实基本相同，就是在整个儿二叉树中寻找到与欲删除节点键值最相近的节点（也即某叶节点），用该节点去替换掉欲删节点即可，如下图1所示：

图1

图1中，z (d) 为删除节点，我们根据二叉搜索树的建立原则对其全部结点顺序进行排序，则必定可以找到如下图2所示的顺序队列：

图2
      这里的n或q节点有可能为空，这并不影响问题的处理方法。在全树中，我们可以用m或p去填充z (d)所占的位置，将m的左子树n接到原先m的位置上，然后将d从树中去掉；或者我们用p去填充z (d)所占据的位置，将p的右子树q接到原先p的位置上，然后将d从树中去掉。这两种方法是等效的，在本函数大多数情况下中所采取的是后一种方法，也即用p去填充z (d)的方法，所以我们只讨论这种方法。只有在一种情况下我们不得不进行前一种方法，那就是在d不存在右孩子的情况下，我们只能用前面的m填充z（d）的位置来进行处理（这种情况我们到后面再讨论）。在进行上述操作之后整个树变成下图3所示的情况：

图3
       这时整颗二叉搜索树的特性也没有破坏，并仍然保持顺序队列，如图4：

图4
        我们来看具体这部分的代码片段：
   _Rb_tree_node_base* __y = __z;   //局部变量定义指针/迭代器y指向待删除节点z
  _Rb_tree_node_base* __x = 0;
  _Rb_tree_node_base* __x_parent = 0;

       首先，我们来确定y在整颗红黑树中的位置，排除两个特殊情况，即y位于最左节点和y位于最右节点处（即y节点分别为树中键值最小和键值最大节点两种情况），这两种情况下，我们可以对y直接进行去除，不需要进行查询替换手续，但是，这两种情况下依然要对x进行定位，以便在后面调整红黑树平衡时使用。始终保持一个原则：x永远指向替换的节点的子节点。
  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. 注意这就是我们前面所说的y(或z) 不存在右孩子的情况，这种情况下x不同的取了y左孩子的值。
    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;
    }
     在上一个else条件中，即是最普通的情况，这种情况下y有两个子节点，处于顺序队列中间，这种情况下我们需要向z的右子树里去寻找键值最接近z的节点（即前面讨论的p节点），并将y指向p，这里程序使用一个while循环进行查找，先令y指向z的右子树的跟，然后一路向左行进，直到找到最左的叶节点，此时就是p所在：
__y = __y->_M_right;   //   __z's successor.  __x might be null.
      while (__y->_M_left != 0)
        __y = __y->_M_left;
       找到p之后y指向p，紧跟着就是将x指向p的右子树（因为到底了，y已经没有左子树了）。这时x有可能为空。
下面开始填充z节点的过程，STL注释解释的比较到位，他说“在z的位置对y进行重新连接”，想想的确如此，在物理位置上没有改变，只是将y与z及其相邻的若干节点进行重新连接而已。这里分两种情况来考虑，一种是一般情况，另一种就是上面提到的，z是红黑树里最右边的节点（键值最大），此种情况下可能需要改变head节点指向的leftmost以及rightmost指针的指向（还记得函数原型中最后两个参数是干什么用的么？就在这里使用）。
       我们首先看到第一种一般情况，就是z不是树里最右边的节点。
if (__y != __z) {          // relink y in place of z.  y is z's successor
此种情况下，开始改变y与z原先的连接，使y代替原先z的位置：
__z->_M_left->_M_parent = __y;  //首先改变与z相连的左孩子，节点其父节点指针的链接，使其指向y，
__y->_M_left = __z->_M_left; //同样将y自身的左孩子与z的左孩子相连
    if (__y != __z->_M_right) { //y不是z的右孩子
      __x_parent = __y->_M_parent; //此时引入__x_parent来，__x_parent的意义就是在调整y结束之后始终指在x的父节点位置。
      if (__x) __x->_M_parent = __y->_M_parent; // 如果x不为空，x中的父节点指针始终等于__x_parent
      __y->_M_parent->_M_left = __x;      // __y must be a child of _M_left， 指针x指向的节点在调整结束后取代y之前的位置，始终是__x_parent的左孩子，见图5：

图5

       现在调整y的右孩子指针，使其指向z的右孩子：
      __y->_M_right = __z->_M_right;
      __z->_M_right->_M_parent = __y; //调整z右孩子的父亲指针使其指向y，至此y的重新连接完毕。
    }
    else //如果y是z的右孩子，属于稍微特殊的一种情况，
      __x_parent = __y;  //这种情况下y自身就是x的父亲即__x_parent
这里还有种特殊情况， 即欲删除的z本身就是整个红黑树的根结点，如下：
    if (__root == __z)
      __root = __y; // 这种情况下，直接令根结点等于y本身即可
    else if (__z->_M_parent->_M_left == __z) // 如果z本身是左孩子，则
      __z->_M_parent->_M_left = __y; // 令z的父亲的左孩子指针指向y
    else
      __z->_M_parent->_M_right = __y; // 令z的父亲的右孩子指针指向y到，这里已经离开y是否z的右孩子这个判断条件了：
    __y->_M_parent = __z->_M_parent; // 修改y所指向的父亲指针，时期重新指向z指向的父亲
    __STD::swap(__y->_M_color, __z->_M_color); // 对换y和z各自指向的节点本身的颜色值，以备下面红黑树平衡时使用，注意这里对换之后，并没有破坏原先树的颜色规则，也即：这行保证了删除之前z是什么颜色的节点，删除之后在树中相同位置的仍然是这种颜色。

       注意，在经过上述行为之后，原先树中z指向的节点是否发生了改变了吗？？？我们可以自己查看，除了颜色值之外，z指向节点的内容并没有发生改变！！！也就是说，只是y所指向的那个节点和z指向节点的相邻周围节点发生了改变，z指向的节点得到了充分的保护。
    __y = __z; // __y now points to node to be actually deleted
  }

       y重新指向了z指向的节点，这一步是为了下面红黑树平衡调整时使用的，而且也正是最终函数返回的实际上被删除的指针！要使用到的关键的一个值就是y指向的节点的颜色值！！！这时，因为上面的对换语句，y指向的节点的颜色值，其实就是之前未变化之前的节点的颜色值，请注意这里，这里很重要，马上就要用到这个颜色值！！！以图来解释就是下图6所示：

图6（注：我们其实只是为比较p和d的颜色值的对换情况而特别举此图中的例子，这种情况我们到后面还要说到。）
我们再来看第二种情况，就是z是红黑树最右边的节点（即y == z）：
  else {                        // __y == __z
    __x_parent = __y->_M_parent; // 指定x的父节点指针
这里与前面情况不同，这就是我们前面讨论的删除的节点不存在右孩子的情况，采用排在排列前面的来填充d这种方法，x此时取其左孩子的值。如图7所示：

图7
    if (__x) __x->_M_parent = __y->_M_parent;   // 如果x不为空，x中的父节点指针始终等于__x_parent，
    if (__root == __z)
      __root = __x; // 如果z指向的是根结点的话，这时直接可知z指向的是树最右边的节点，即键值最大的节点，此时z后面已没有节点，所以直接令x指向根。
    else
      if (__z->_M_parent->_M_left == __z)
        __z->_M_parent->_M_left = __x; // 如果z本身是左孩子，则令z的父亲的左孩子指针指向x，如图7。
      else
        __z->_M_parent->_M_right = __x; // 否则令z的父亲的右孩子指针指向x 

      这里往下，需要开始调整红黑树中的__leftmost和__rightmost的值：
    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，这种情况如下图8：

图8
      else
        __leftmost = _Rb_tree_node_base::_S_minimum(__x);
这种情况如下图9，此时__leftmost指向x子树中最小的那个节点：

图9
     同理，下面开始调整红黑树中的__rightmost的值：
    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，这种情况如下图10：

图10
      else                      // __x == __z->_M_left
        __rightmost = _Rb_tree_node_base::_S_maximum(__x);
  }
这种情况如下图11，此时__leftmost指向x子树中最大的那个节点：

图11
      注意上面的这大段代码，始终回避y指针，而直接用z指针对其进行操作，这样做的目的是显而易见的：因为y == z，所以对哪个进行操作都是一样的。为简便起见我们直接使用z。

2. 调整剩余节点使其重新达到平衡
       好了，有关去除z指向节点的所有情况分析完毕，下面着重来看这个函数中最恐怖的部分：因为去掉一个结点之后，剩余的这颗树的平衡很有可能被破坏掉，所以我们来调整这颗树使其继续达到平衡。

     首先我们来回忆红黑树平衡性原则：
1． 红色节点不能彼次相邻；
2． 在红黑树中，每个分支路径上的黑色节点数目总和相等，或者说：从根结点开始到每个叶节点为止，所遇到的黑色节点数目相等。

       有了这两条最主要的原则，我们在再来衡量我们剩余的树的平衡标准就清晰了，看前面的图6所示的情况，p与d对换了各自的颜色值，p节点取代了原先实际欲删除的d节点的位置，但是p节点的颜色值仍旧保持了删除之前d节点的颜色值，而去除之后的d节点的颜色值，正是删除前p节点的颜色值。所以很明显，真正有可能破坏树的平衡性的，并不是取决于d节点，而取决于代替d节点的p节点的颜色值，在本函数中，恰恰正是指针y所指向的颜色值（y指向d没错，但是此时的d的颜色值已经是之前的p的颜色值了）。

       当y指向的颜色值是红色的话，因为黑色节点的数目没有发生变化，所以整颗树依然保持平衡，我们什么也不用干。但当y指向的颜色值是黑色的话，全树中黑色节点数目少了1，平衡被打破，我们才需要重新调整平衡性，这就复杂了，又分了好多种情况。下面一边看代码一边进行分析：
if (__y->_M_color != _S_rb_tree_red) {  // 这就是判断剩余树是否平衡的关键依据，只有y指向的节点颜色值不是红色时才需要进行平衡性调整，否则什么也不用干。

       注意下面这个庞大的while循环它是这个函数中最复杂最难理解的部分，初读到这里时会很费解，为什么这里要使用while循环呢？这牵扯到后面我们会分析到的一种最坏的情况发生，就是我们无法简单的几步旋转变色操作就达到平衡的情况，我们还需要不停的向其父节点求索，一直到平衡条件出现，或者干脆一直上溯到根结点为止。这种极其特殊且困惑的情况我们到后面再谈。
    while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) // x指向的节点颜色为黑时，进行下面的循环判断。为什么要进行这样的判断？还是以图6为例，如果x指向的q节点是不是黑色而是红色的话，那么我们只需要将q颜色值变成黑色，整颗树又达到了新的平衡，根本不需要再进行下面的操作，所以，我们需要把这种最简单的情况排除掉。注意：下面讨论的情况全部都是x节点为黑的情况。
       这时，经过前面的去除节点操作后，指针__x_parent已经指向了x节点的父亲位置。所以进行下面的判断：下面我们来分析y被从树中拿掉后，整颗树不平衡的根源：如下图12所示：

图12
       可以明显看出，所有含有x指向的q节点的路径，在去除操作之后路径上黑色节点数目都减少1，而全树其他路径上黑色节点数目没发生变化。
       所以，在保持其他路径上黑结点数目不变的条件下，需要对相关路径上的节点进行变色和旋转等方法调整x节点路径上黑结点数目，而与此相关的节点包括x的父亲x_parent以及其兄弟节点，必要时甚至包括其兄弟节点的子树上其他的节点；下面对其具体进行分析。
      if (__x == __x_parent->_M_left) { // 这是判断x节点是否本身是一个左孩子，这是一个前提条件，当然还有可能x节点是右孩子，我们在后面会讨论到。
        _Rb_tree_node_base* __w = __x_parent->_M_right; // 新定义一个临时指针w，指向x的兄弟节点，下面重点对其兄弟节点w的颜色情况作讨论：
        if (__w->_M_color == _S_rb_tree_red) { // 如果w为红节点，这里隐含了一种限定，根据平衡准则1，两个红色节点不能相邻，所以__x_parent指向的节点必为黑（不单是g节点，而且其孩子a1和a2也必全黑，这种情况是唯一确定的，后面还要讨论当w不是红色的情况，那就要稍复杂抽象一些）。这种情况见下图13：

图13
          __w->_M_color = _S_rb_tree_black;
          __x_parent->_M_color = _S_rb_tree_red;
          _Rb_tree_rotateleft(__x_parent, __root);
          __w = __x_parent->_M_right;   // 旋转之后w虽然从a节点转而指向a1节点，但从总体来看是仍然指向了__x_parent的右节点，仍是x节点的兄弟节点。
       从图13可以看出，旋转之后各路径上黑色节点总数并没有发生变化，那么这样旋转变换的意义何在？注意，这样旋转之后，x指向的节点实际上多了一层红色节点做缓冲，这就为后面的操作提供了方便，我们可以看出只要别的规则不违背的话，将__x_parent指向的g节点直接变黑，x路径就可以平衡了，但是这样一来w指向的节点的路径中黑色节点数目可能多了1，又有不平衡产生，所以我们还不能如此简单的变色处理就万事大吉了，我们还得进一步分析现在的w指向的节点以及其子树上红黑节点分布的情况，借以次做出判断和调整，但不管怎么说，这样做算是开了个头。
        }
       这个条件判断结束，其实还隐含了另外一种情况的产生，那就是啊：如果w为黑节点该怎么办？这种情况其实又分多种可能，单就看__x_parent指向的g节点的话，g的颜色可能为红，也可能为黑。而且w指向的a节点的左右孩子的颜色可能也并不确定。
       其实，加上第一个if (__w->_M_color == _S_rb_tree_red) 条件变换之后所得到的状态，上述几种情况可以找到共同点，那就是w指向的全都是黑色节点，根据着共同点，我们可以先转而讨论w指向节点平衡情况，如图14：

 图14
通过图我们可以看出，图中左边（即图13变换之后的结果）可以归入图中间这种情况中，这样一来我们首先应该考虑的，是x节点的兄弟w节点的左右孩子颜色情况来考虑，这就是下面的代码要考虑的：
        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的左右孩子全都没有红颜色（可以为空）时，如下图15所示：

 图15
          __w->_M_color = _S_rb_tree_red;
          __x = __x_parent;
          __x_parent = __x_parent->_M_parent;
       观察这里的代码，这种情况下，我们将w指向的节点变成红色，这样包含g的所有路径上黑节点数目就都减少1，然后将x和__x_parent指针全部上溯一个，将x指向g，__x_parent指向g的父节点，这样问题看似又回到了最初的状态，不过黑色节点数目少1的路径队伍壮大了，这样我们跳出该条件语句，继续在while中执行循环，直到遇到可以找到使其平衡的条件出现，或者就一直上溯到根结点，如果x真的上溯到根结点的话，那么经过如此调整之后，整个树一定保持平衡。此时退出循环。
        } else { // 这种情况是当w的左右孩子中有红色节点出现，这种情况稍微复杂一些，首先我们确定到底是w的左孩子还是右孩子是红色，还是两个孩子都是红色，
          if (__w->_M_right == 0 ||
              __w->_M_right->_M_color == _S_rb_tree_black) { // 当w指向的节点的右孩子为黑 ，如图16所示：

图16
            if (__w->_M_left) __w->_M_left->_M_color =