算法导论P167页关于红黑树插入的伪代码

Question

如果红黑树是这种形式的

最下面的红节点表示新插入的节点，请问：这个过程和伪代码是如何对应的？另外，我看伪代码执行了color[y]=RED的情形后，应该回到while（color[p[z]]==Red）那个地方，我看伪码怎么要执行12-14行呢？这是不对的啊？？

问题2：针对这个代码，谁能帮我描述一下代码的执行过程？我先说一下我的思路：y=right[p[p[z]]],此时的y为哨兵节点，color[y]=BLACK，请问如果12-14行包含在第二个else if(z=right[p[z]])中时，程序如何执行到12-14行？

Answer 1

if color[y]=RED后面的then是if正确后执行的，12-14行是与这个if对应的else（即它是BLACK）， 所以伪代码没有执行到12-14行，而是进行另一个while循环，也许是刚好翻页了，缩进看的不是很清楚。 在翻页后可以看到的那个else是跟第一个if对应的，而12-14行是和else if z = right[p[z]]这一行的else对应的，是和这个if相同缩进的。 你也可以详细看看后面的情形1,2,3，就理解了具体步骤，而不用管他这个伪代码到底是什么情况。

Answer 2

可以具体说说红黑树的执行情况：
插入操作：最为关键的是叔结点的颜色：

具体的情况大致有下面两种：

这种情况，叔结点为红色（黑色也无所谓啦，反正都有y->color=black，最终都会染为黑色的）。
此时最重要的是，插入的结点D为外结点。

处理的时候：相当于A这个结点的黑色下放到B,C这两个结点，于此同时，原来新插入的结点D相当于右边那个树中的E，由此，新插入的D->E->.....->ROOT,这样往树的根部进行上升，不破坏红黑树的性质，对应的代码是：

if (y->color==red) //y为叔结点
{
  z->parent->color=black;
  y->color=black;
  z->parent->parent->color=red;
  z=z->parent->parent;
  z->bh++;
}

2、z为内结点（新插入的点为内结点）

我们需要外旋，于此同时，要保证新插入的点d的相对黑高不变。注意到外旋出来，d会沿树上升，我们要让相对黑高不变。执行如下代码：

if (z==z->parent->right)
{
  z=z->parent;
  left-rotate(T,z);
}

接着完成递归，一定要让新插入的结点沿树上升。
在红黑树中让结点沿树上升的方法就是执行旋转。

以I为中心旋转

z->parent->color=black;
z->parent->parent->color=red;
right-rotate(T，z->parent->parent);