algorithm - 红黑树旋转 : When I have y = x. 向右； x.右=y.左。 y.left.p = x 写成 x.right.p = x 是一样的吗

Question

在CLRS中，作者通过以下伪代码介绍了红黑树中的旋转操作:

LEFT-ROTATE(T, x)

    y = x.right        # Line 1
    x.right = y.left   # Line 2
    if y.left ≠ T.nil  # Line 3
        y.left.p = x   # Line 4
    y.p = x.p
    if x.p == T.nil
        T.root = y
    elseif x == x.p.left
        x.p.left = y
    else x.p.right = y
    y.left = x
    x.p = y

其中属性 .left、.right、.p 对应于其左、右子节点及其父节点。 T 是树。

我的主要问题在于第 3 行和第 4 行:

1. 为什么需要第 3 行的 if 条件？书上说NIL实际上是红黑树的叶子，所以我假设NIL也可以有父指针。这些代码在没有第 3 行的情况下仍然可以工作。

2. 有了第 1 行和第 2 行，我可以将第 4 行写成 x.right.p = x 吗？如果它们实际上是相同的，那么作者选择将其写为y.left.p = x有什么原因吗？

我的直觉是，x.right.p = x 与 y.left.p = x 不同。但是，我对此找不到很好的解释。我检查了 pointers 的定义，但在我用谷歌搜索了很多之后仍然很困惑......

Answer 1

注意:我没有在每个图表上放置父关系箭头以消除一些困惑。

空节点不能有父节点，如图所示。here中有更深入的解释

1. 如图所示，如果y.left，则第3行的检查是不必要的。绝不为空。如果不能保证这一点，则此检查是为了防止“空指针取消引用”错误。

2. 使用的选择y.left.p = x是用户偏好。对我来说，这就清楚多了。我们正在制作"y left subtree into x right subtree" 。

@HolderRoy 展示的示例可以工作，但它会进行额外的分配以可能存储 y.left指针，foreach 函数调用。