红黑树删除代码第23行x->parent=y赋值的必要性疑问

01 void RedBlackTree::deleteNode(Node *z)
02 {
03     Node *y = z;
04     Color yOriginalColor = y->color;
05     Node *x;
06     if (z->left == sentinel)
07     {
08         x = z->right;
09         transplant(z, z->right);
10     }
11     else if (z->right == sentinel)
12     {
13         x = z->left;
14         transplant(z, z->left);
15     }
16     else
17     {
18         y = minimum(z->right);
19         yOriginalColor = y->color;
20         x = y->right;
21         if (y->parent == z)
22         {
23             x->parent = y;  // WHY??
24         }
25         else
26         {
27             transplant(y, y->right);
28             y->right = z->right;
29             y->right->parent = y;
30         }
31         transplant(z, y);
32         y->left = z->left;
33         y->left->parent = y;
34         y->color = z->color;
35     }
36 
37     delete z;
38 
39     if (yOriginalColor == Color::BLACK)
40     {
41         deleteFixUp(x);
42     }
43 }

问题描述 #

在上述红黑树deleteNode函数中，第20行将y->right赋值给x，第23行又执行x->parent = y的赋值操作。我疑惑该赋值是否冗余，因为x的父节点本应就是y。此外，我无法理解CLRS教材中的相关解释：为何x.p会指向z？当y从原位置移动到z的位置时，y的子节点x不应仍依附于y吗？同时也不理解该赋值操作与x是否为sentinel节点有何关联。

核心解析 #

• 先明确场景：这段代码处理的是z有左右两个子节点的情况，我们找到z右子树的最小节点y来替代z。当y的父节点就是z时（也就是y是z的直接右孩子），后续会把y移到z的位置。
• 为什么这行代码不是冗余的？
  1. 哨兵节点的特殊情况：很多红黑树实现里用全局共享的哨兵节点代替空指针，这个哨兵的parent指针不会自动维护为y。如果不手动设置x->parent = y，后续执行deleteFixUp(x)时，会因为x的父指针错误，导致找兄弟节点、判断路径等逻辑全部出错。
  2. 统一处理边界场景：即使x是普通节点，当y是z的直接右孩子时，我们没有执行else分支里的transplant(y, y->right)——这步操作本来会更新x的父指针，但这里跳过了。虽然普通节点的父指针原本就是y，但加上这行代码能统一兼容哨兵和普通节点的情况，避免遗漏指针修正。
• 关于CLRS的解释：教材里说x.p会指向z是容易误解的表述——当y是z的右孩子时，如果x是哨兵，它的父指针可能未正确初始化，或者没有绑定到y。如果不手动赋值，后续y移到z的位置后，x的父指针会处于错误状态，影响红黑树的修复逻辑。
• 总结：这行代码的核心作用是统一修正x的父指针，兼容哨兵节点的特殊实现，保证后续deleteFixUp能基于正确的父子关系修复红黑树性质，完全不是冗余操作。

内容的提问来源于stack exchange，提问作者Zack