红黑树旋转：当我有y = x.right时；x.right = y.left。将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。但是，我对此找不到很好的解释。我已经检查了指针的定义，但是在谷歌搜索很多之后，它仍然很令人困惑。

Answer 1

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

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

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

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

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