关于 Red-Black 树删除的问题（z 有 2 children）（pre-fixDelete）

Question

代码源 - https://github.com/Bibeknam/algorithmtutorprograms/blob/master/data-structures/red-black-trees/RedBlackTree.cpp

    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
    }

问题

1. Local Class TNull -（如果 y->right 是 TNull）在这个 class 函数中，TNull 是简单传递给 [=16= 的本地指针];是不是改变 x 的 parent 也改变了本地 TNull 的 parent?
1. 丢失 Y - 这部分是为了在 z 的右子树中的最小值不是直接 children 的情况下执行。稍后它将被放置在 z 的位置。该段不会仅旋转 y->right / x 直到到达 z 的位置，而不是 y / minimum 吗？
1. 需要重新着色 - Iirc，重新着色也会在后面的 fixDelete() 函数调用中发生，为什么需要这样做？

请多多包涵，我做这种事情的速度很慢，实在是束手无策。这是我第一次在这里问。谢谢。

Answer 1

关于你的问题

是的，这可能发生，TNull 的父级已设置，作者评论说这是他们利用的故意设计选择。
y 正在移动到 z 所在的位置，这只是修复了 y 所以它的指针是 z 的指针。 s
没有。本质上，当要删除的节点有 2 个子节点时，您会找到后继节点或前导节点（必须有 0 个或 1 个子节点）并交换节点。然后删除后继或前导节点位置的节点。交换了前任或后继节点，保留了树排序。但重要的是在交换节点时，颜色不会交换，它必须被保留 所以 red-black 树属性仍然是正确的。这就是 y_original_color 的用途。

关于 Red-Black 树删除的问题（z 有 2 children）（pre-fixDelete）

Questions regarding Red-Black Tree Deletion (z has 2 children) (pre-fixDelete)

c++

data-structures

red-black-tree