CLRS红黑树删除

Question

我从关于红黑树的CLRS章节中复制了伪代码，也是基于this实现的。我复制的代码在删除根节点时不能正常工作(根节点在修复之前没有改变，我认为这是由于错误的移植)，我找不出原因。

RBTNode* Custom_Delete(RBTNode* tree, RBTNode* z) {
    RBTNode *x, *y;
    y = z;
    int y_og_color = y->color;

    if (z->left == NIL){
        x = z->right;
        transplant(tree, z, z->right);
    } else if (z->right == NIL){
        x = z->left;
        transplant(tree, z, z->left);
    } else {
        y = RBTreeMinimim(z->right);
        y_og_color = y->color;
        x = y->right;
        if (y->parent == z){
            x->parent = y;
        } else {
            transplant(tree, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(tree, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (y_og_color == BLACK) {
        RBTreeDeleteFixUp(tree, x);
    }
    return y;
}

void transplant(RBTNode* root, RBTNode* u, RBTNode* v)
{
    if (u->parent == NIL)
        {root = v;}
    else if(u == u->parent->left)
        {u->parent->left = v;}
    else
        {u->parent->right = v;}
    v->parent = u->parent;
}

Answer 1

代码本身不是错误，I've just passed root pointer to transplant() incorrectly。它应该是void transplant(RBTNode* &root, RBTNode* u, RBTNode* v)，这样根指针在被delete()调用后实际上可以改变。