Red-black 树旋转：当我有 y = x.right; x.right = y.left。 y.left.p = x 和 x.right.p = x 一样写吗
Red-black Tree Rotation: When I have y = x.right; x.right = y.left. Is it the same to write y.left.p = x as x.right.p = x
在CLRS中，作者通过如下伪代码介绍了red-black树中的旋转操作：
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对应其左，右child，其parent。 T是树。
我的主要问题在第 3 行和第 4 行：
为什么要有第3行的if条件？书上说NIL其实是red-black树的一片叶子，所以我假设NIL也可以有parent指针。这些代码在没有第 3 行的情况下应该仍然有效。
有了第1行和第2行，我可以把第4行写成x.right.p = x吗？如果它们实际上是相同的，那么作者选择将其写为y.left.p = x是否有原因？
我的直觉是 x.right.p = x 不同于 y.left.p = x。但是，我找不到很好的解释。
我查看了pointers的定义，但在我搜索了很多之后仍然很混乱......
看了你描述的最后一行，我发现你没有学习指针，所以你可能很难理解为什么我们需要判断某物是否T.nil。不过我还是尽量回答你的问题，希望能解释清楚。
在数据结构上，肯定不用第3行，反正要调整y.left.p。
然而，对于给定的语言，仅以C/C++为例，我们对叶和根的父级使用NULL或nullptr，这意味着它什么都不是。试想一下，为了节省无用的叶子，是否需要花费与树节点一样多的内存？当然不是。所以我们把它标记为NULL指针，没有任何意义，也没有p，left或right。
结论来了，要不要在第3行判断T.nil，要看你的实现了。
是的，你可以。在x.right = y.left之后，x.right和y.left暂时是一样的，所以x.right.p和y.left.p是一样的。
第2~4行也可以这样写：
beta = y.left;
x.right = beta;
if beta != T.nil
beta.p = x;
注意：为了消除一些混乱，我没有在每个图表上都加上父关系箭头。
空节点不能有父节点，如图所示。
here
中有更深入的解释
如图所示，如果 y.left NEVER null，则无需检查第 3 行。如果不能保证这一点，此检查是为了防止 "null pointer dereference" 错误。
使用y.left.p = x的选择是用户偏好。对我来说，它更清楚了。我们正在制作 "y left subtree into x right subtree"。
@HolderRoy 显示的示例将起作用，但它会进行额外分配以可能存储 y.left 指针，foreach 函数调用。
在CLRS中，作者通过如下伪代码介绍了red-black树中的旋转操作：
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对应其左，右child，其parent。 T是树。
我的主要问题在第 3 行和第 4 行：
为什么要有第3行的if条件？书上说NIL其实是red-black树的一片叶子，所以我假设NIL也可以有parent指针。这些代码在没有第 3 行的情况下应该仍然有效。
有了第1行和第2行，我可以把第4行写成
x.right.p = x吗？如果它们实际上是相同的，那么作者选择将其写为y.left.p = x是否有原因？
我的直觉是 x.right.p = x 不同于 y.left.p = x。但是，我找不到很好的解释。
我查看了pointers的定义，但在我搜索了很多之后仍然很混乱......
看了你描述的最后一行，我发现你没有学习指针，所以你可能很难理解为什么我们需要判断某物是否T.nil。不过我还是尽量回答你的问题，希望能解释清楚。
在数据结构上，肯定不用第3行，反正要调整y.left.p。
然而，对于给定的语言，仅以C/C++为例，我们对叶和根的父级使用NULL或nullptr，这意味着它什么都不是。试想一下，为了节省无用的叶子，是否需要花费与树节点一样多的内存？当然不是。所以我们把它标记为NULL指针，没有任何意义，也没有p，left或right。
结论来了，要不要在第3行判断T.nil，要看你的实现了。
是的，你可以。在
x.right = y.left之后，x.right和y.left暂时是一样的，所以x.right.p和y.left.p是一样的。第2~4行也可以这样写：
beta = y.left;
x.right = beta;
if beta != T.nil
beta.p = x;
注意：为了消除一些混乱，我没有在每个图表上都加上父关系箭头。
空节点不能有父节点，如图所示。 here
中有更深入的解释如图所示，如果
y.leftNEVER null，则无需检查第 3 行。如果不能保证这一点，此检查是为了防止 "null pointer dereference" 错误。使用
y.left.p = x的选择是用户偏好。对我来说，它更清楚了。我们正在制作"y left subtree into x right subtree"。
@HolderRoy 显示的示例将起作用，但它会进行额外分配以可能存储 y.left 指针，foreach 函数调用。