algorithm - 红黑树旋转：当我有 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. 但是，我找不到一个很好的解释。我已经检查了指针的定义，但是在我搜索了很多之后它仍然很混乱......

标签： algorithmdata-structuresred-black-tree

Answer 1

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

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

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

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

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