红黑树伪代码冗余
在算法第三版的介绍中,它们具有红黑树删除的伪代码实现。这里是...
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.left)
else
y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y // <--------- why????
else
RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
TREE-MINIMUM只是在树中找到最小值,RB-TRANSPLANT接受第二个参数的父级,并使其指向第三个参数,第三个参数的父级为第二个参数的父级。
根据我的评论,他们测试y.p是否为z,如果是,则将x.p设置为y。但是x已经是y.right,所以这就像说y.right.p = y,但是y.right.p已经是y!他们为什么要这样做?
这是他们的解释...
“但是,当y \的原始父级为z时,我们不希望x.p指向y \的原始父级,因为我们正在从树中删除该节点。由于节点y将向上移动以在树中占据z \的位置,因此即使x == T.nil,在第13行中将x.p设置为y也会导致x.p指向y \的父级的原始位置。”
所以他们想让x \的父母为y ...已经是y ...
没有找到相关结果
已邀请:
1 个回复
磨标烫徽啪