有关红黑树删除的问题（Z有2个孩子）（固定前）

Question

代码源 -

    y = z;
    int y_original_color = y->color;
    if (z->left == TNULL) {
        x = z->right;
        rbTransplant(z, z->right);
    } else if (z->right == TNULL) {
        x = z->left;
        rbTransplant(z, z->left);
    } else {
        y = minimum(z->right);
        y_original_color = y->color;
        x = y->right;                            
        if (y->parent == z) {
            x->parent = y;                       \\ [1] Local Class TNull
        } else {
            rbTransplant(y, y->right);           \\ [2] Losing Y
            y->right = z->right;
            y->right->parent = y;
        }

        rbTransplant(z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;                     \\ [3] Need of Recoloring
    }

Questions

• 1. 本地类tnull-（如果 y-＆gt; right 是 tnull ），则TNULL是本地指针，简单地传递给 x x ; x 的更改 parent 也不更改本地 tnull ？
  的父。
• 1. 失去y-如果 z 的最低符号不是直接的孩子，则本节应执行。稍后将其放置在 z 的位置。此段不仅只有Pivot y-＆gt; right/x 直到达到 z 的位置，而不是 y/minumim ？<？？ /li>
• 1. 需要重新上色-IIRC，重新上色也会在以后的 fixdelete（）函数调用中发生，为什么需要此？

请忍受我，我对这种事情很慢，我真的处于智慧。这是我第一次在这里问。谢谢。

Answer 1

在您的问题上

• 可能会发生，Tnull的父母是设定的，作者指出，这是他们利用的故意设计选择。
• y正在移动到Z所在的位置，这只是修复Y，因此它的指针就是Z所拥有的。 S。
• 从本质上讲，当要删除的节点有2个孩子时，您会发现继任者或前身节点（必须具有0或1个孩子）并交换节点。然后，您可以在连续或前身节点位置上删除节点。交换了前身或后继节点，保留树排序。但是重要的是在交换节点，颜色不换成，必须保留，因此红黑树的特性仍然正确。
  这就是y_original_color的目的。