您的位置: 首页  >  IT文章  >  《算法导论》中红黑树删除结点的伪代码没看明白,该怎么处理

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

分类: IT文章 • 2022-06-06 22:00:58
《算法导论》中红黑树删除结点的伪代码没看明白
伪代码如下
C/C++ code

RB-DELETE(T, z)

1 if left[z] = nil[T] or right[z] = nil[T]
2     then y ← z
3     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] ← x
10    else if y = left[p[y]]
11         then left[p[y]] ← x
12         else right[p[y]] ← x
13 if y ≠ z
14     then key[z] ← key[y]
15     copy y's satellite data into z
16 if color[y] = BLACK
17     then RB-DELETE-FIXUP(T, x)
18 return y

RB-DELETE-FIXUP(T, x)

1 while x ≠ root[T] and color[x] = BLACK
2     do if x = left[p[x]]
3        then w ← right[p[x]]
4            if color[w] = RED
5                then color[w] ← BLACK                                    // Case 1
6                     color[p[x]] ← RED                                   // Case 1
7                     LEFT-ROTATE(T, p[x])                                 // Case 1
8                     w ← right[p[x]]                                     // Case 1
9            if color[left[w]] = BLACK and color[right[w]] = BLACK
10              then color[w] ← RED                                       //Case 2
11                    x ← p[x]                                            //Case 2
12              else if color[right[w]] = BLACK
13                   then color[left[w]] ← BLACK                          //Case 3
14                        color[w] ← RED                                  //Case 3
15                        RIGHT-ROTATE(T, w)                               //Case 3
16                        w ← right[p[x]]                                 //Case 3
17                  color[w] ← color[p[x]]                                //Case 4
18                  color[p[x]] ← BLACK                                   //Case 4
19                  color[right[w]] ← BLACK                               //Case 4
20                  LEFT-ROTATE(T, p[x])                                   //Case 4
21                  x ← root[T]                                           //Case 4
22           else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK

删除的结点是z，我的疑问是RB-DELETE-FIXUP(T, x)中的x到底指向什么，请懂的人就下面一个图给我解释下就行了。我自己是越看越晕。根据这个博客http://blog.****.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 
图不解释了，建议你去网上搜搜，有很详细的图解。

相关推荐