gpt4 book ai didi

algorithm - 红黑树伪代码冗余

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:23:37 25 4
gpt4 key购买 nike

在算法第三版简介中,他们有一个红黑树删除的伪代码实现。这是...

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!他们为什么要这样做?

这是他们的解释......

“When y's original parent is z, however, we do not want x.p to point to y's original parent, since we are removing that node from the tree. Because node y will move up to take z's position in the tree, setting x.p to y in line 13 causes x.p to point to the original position of y's parent, even if x == T.nil.”

所以他们想让 x 的父级保持为 y...它已经是 y...

最佳答案

他们在文本中声明 x 也可以为 Nil,即当 y.right 为 Nil 时。似乎 Nil 在此代码中也由一个节点表示,他们不想留下悬空指针。

关于algorithm - 红黑树伪代码冗余,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5739730/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com