《算法导论》中红黑树删除结点的伪代码没看明白,该怎么处理

《算法导论》中红黑树删除结点的伪代码没看明白
伪代码如下

C/C++ code

RB-DELETE(T, z)1 if left[z] = nil[T] or right[z] = nil[T]2     then y ← z3     else y ← TREE-SUCCESSOR(z)4 if left[y] ≠ nil[T]5     then x ← left[y]6     else x ← right[y]7 p[x] ← p[y]8 if p[y] = nil[T]9     then root[T] ← x10    else if y = left[p[y]]11         then left[p[y]] ← x12         else right[p[y]] ← x13 if y ≠ z14     then key[z] ← key[y]15     copy y's satellite data into z16 if color[y] = BLACK17     then RB-DELETE-FIXUP(T, x)18 return yRB-DELETE-FIXUP(T, x)1 while x ≠ root[T] and color[x] = BLACK2     do if x = left[p[x]]3        then w ← right[p[x]]4            if color[w] = RED5                then color[w] ← BLACK                                    // Case 16                     color[p[x]] ← RED                                   // Case 17                     LEFT-ROTATE(T, p[x])                                 // Case 18                     w ← right[p[x]]                                     // Case 19            if color[left[w]] = BLACK and color[right[w]] = BLACK10              then color[w] ← RED                                       //Case 211                    x ← p[x]                                            //Case 212              else if color[right[w]] = BLACK13                   then color[left[w]] ← BLACK                          //Case 314                        color[w] ← RED                                  //Case 315                        RIGHT-ROTATE(T, w)                               //Case 316                        w ← right[p[x]]                                 //Case 317                  color[w] ← color[p[x]]                                //Case 418                  color[p[x]] ← BLACK                                   //Case 419                  color[right[w]] ← BLACK                               //Case 420                  LEFT-ROTATE(T, p[x])                                   //Case 421                  x ← root[T]                                           //Case 422           else (same as then clause with "right" and "left" exchanged)23 color[x] ← BLACK

删除的结点是z，我的疑问是RB-DELETE-FIXUP(T, x)中的x到底指向什么，请懂的人就下面一个图给我解释下就行了。我自己是越看越晕。根据这个博客http://blog.csdn.net/v_JULY_v/article/details/6284050 下面这个图是属于case1的。但是我觉得x指向第一幅图的right[13]，然后再往下看RB-DELETE-FIXUP(T, x)就不对劲了。
下面是删除结点12，第一幅是原图，第二幅是删除后的图，就这个图和伪代码给我解释下好了，主要是解释x,y均指的哪个



[解决办法]
RB-DELETE-FIXUP(T, x) // T是要删除树根节点 x是要删除的树上的一个节点

1 while x ≠ root[T] and color[x] = BLACK //如果x不是树的根节点并且x节点颜色不是黑色
2 do if x = left[p[x]] // 如果x为父节点的左边孩子
3 then w ← right[p[x]] // 将父节点的右汉字赋值给w
4 if color[w] = RED // 如果w的颜色为红色
5 then color[w] ← BLACK // 则修改颜色为黑色
6 color[p[x]] ← RED // 父节点颜色修改为红色
7 LEFT-ROTATE(T, p[x]) // 左旋转x节点的父节点
8 w ← right[p[x]] // 将父节点右边孩子赋值给w 
图不解释了，建议你去网上搜搜，有很详细的图解。

查看更多 下一篇