伙计们,我正在尝试为红黑树实现删除算法,但我在理解该算法的第三行时遇到问题(来自“算法简介”第二版一书):
1 如果 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 3≠ z
14 then key[z] ← key[y]
15 复制 y 的卫星数据到 z
16 如果 color[y] = BLACK
17 然后 RB-DELETE-FIXUP(T, x)
18 返回 y
首先,这本书中没有任何地方解释了 TREE-SUCCESSOR 应该是什么样子(没有算法),但我找到了这个页面:如果我用 11、2、1、7、5、8 输入这个算法,14,15,4 然后尝试删除 7 它找到前任,但如果我尝试删除 11 它找到后继。那是我无法理解的。为什么有时需要前任,有时需要继任者?做出此决定时考虑了哪些标准?节点的颜色?
谢谢你。
PS我也不太明白第13行写的是什么。这是否意味着如果y有三种颜色(既不是黑色也不是红色)或其他颜色?