红黑树-删除

Question

我已经为RBT实现了删除功能(基于Cormen)，它看起来很有效，但是对删除+打印树的测试却给了我错误的答案。我花了几个小时找可能出了什么问题，但什么也找不到.

下面是按预设顺序打印树的func：

void print_out(rbt_node *root, rbt_node *NIL)
{
    if(root != NIL)
    {
        printf("%d %s ", root->key, root->data.c_str());
        if(root->color == BLACK)
            printf("black ");
        else
            printf("red ");
        if(root->parent != NIL)
            printf("%d ",root->parent->key);
        else
            printf("- ");
        if(root->left != NIL)
            printf("%d ",root->left->key);
        else
            printf("- ");
        if(root->right != NIL)
            printf("%d ",root->right->key);
        else
            printf("- ");
        printf("\n");

        print_out(root->left, NIL);
        if(root->right != NIL)
        {
            print_out(root->right, NIL);
        }
    }
}

下面是要删除的其他重要内容：

rbt_node *NIL = new rbt_node;
NIL->color = BLACK;
NIL->left = NIL->parent = NIL->right = NIL;

rbt_node *tree_minimum(rbt_node *node, rbt_node *NIL)
{
    while(node->left != NIL)
        node = node->left;

    return node;
}

rbt_node *tree_succesor(rbt_node *node, rbt_node *NIL)
{
    if(node->right != NIL)
        return tree_minimum(node->right, NIL);

    rbt_node *helper = node->parent;
    while(helper != NIL && node == helper->right)
    {
        node = helper;
        helper = helper->parent;
    }

    return helper;
}

void delete_fixup(rbt_node *&root, rbt_node *&target, rbt_node *NIL)
{
    rbt_node *helper = NIL;
    while(target != root && target->color == BLACK)
    {
        if(target == target->parent->left)
        {
            helper = target->parent->right;
            if(helper->color == RED)
            {
                helper->color = BLACK;
                target->parent->color = RED;
                left_rotate(root, target->parent, NIL);
                helper = target->parent->right;
            }
            if(helper->left->color == BLACK && helper->right->color == BLACK)
            {
                helper->color = RED;
                target = target->parent;
            }
            else if(helper->right->color== BLACK)
            {
                helper->left->color = BLACK;
                helper->color = RED;
                right_rotate(root, helper, NIL);
                helper = target->parent->right;
            }
            else
            {
                helper->color = target->parent->color;
                target->parent->color = BLACK;
                helper->right->color = BLACK;
                left_rotate(root, target->parent, NIL);
                target = root;
            }
        }
        else
        {
            helper = target->parent->left;
            if(helper->color == RED)
            {
                helper->color = BLACK;
                target->parent->color = RED;
                right_rotate(root, target->parent, NIL);
                helper = target->parent->left;
            }
            if(helper->right->color == BLACK && helper->left->color == BLACK)
            {
                helper->color = RED;
                target = target->parent;
            }
            else if(helper->left->color== BLACK)
            {
                helper->right->color = BLACK;
                helper->color = RED;
                left_rotate(root, helper, NIL);
                helper = target->parent->left;
            }
            else
            {
                helper->color = target->parent->color;
                target->parent->color = BLACK;
                helper->left->color = BLACK;
                right_rotate(root, target->parent, NIL);
                target = root;
            }
        }
    }

    target->color = BLACK;
}

void rbt_delete(rbt_node *&root, int key, rbt_node *NIL)
{
    rbt_node *victim = to_delete(root, key, NIL);
    if(victim != NIL)
    {
        rbt_node *help_one = NIL;
        rbt_node *help_two = NIL;
        if(victim->left == NIL || victim->right == NIL)
            help_one = victim;
        else
            help_one = tree_succesor(victim, NIL);

        if(help_one->left != NIL)
            help_two = help_one->left;
        else
            help_two = help_one->right;

        help_two->parent = help_one->parent;

        if(help_one->parent == NIL)
            root = help_two;
        else if(help_one == help_one->parent->left)
            help_one->parent->left = help_two;
        else
            help_two->parent->right = help_two;

        if(help_one != victim)
        {
            victim->key = help_one->key;
            victim->data = help_one->data;
        }

        if(help_one->color == BLACK)
            delete_fixup(root, help_two, NIL);
    }

    root->color = BLACK;
}

Answer 1

至少，海事组织，你的print_out并没有真正按照它应有的方式工作。具体的问题是它试图(直接)打印子节点的数据。

当您处理二叉树时(任何类型的-不平衡、AVL、RB等)遍历通常看起来大致如下：

void print_out(node *current_node) { 
    if current_node != NIL {
        show_data(current_node);

        print_out(current_node->left);
        print_out(current_node->right);
   }
}

也就是说，这是预先命令；与递归调用print_out相比，post或order只是重新排列print_out的问题(对于post-order，它是在它们之后出现的，是它们之间的顺序)。

但是，特别是，print_out不应该与左或右子树有任何关系，只应该将它们作为递归调用中的参数传递。它通常也不应该检查它们是否为NIL/NULL --它应该只进行递归调用，并让递归调用中的if (current_node != NIL)句柄处理我们已经到达叶节点的可能性。

如果你愿意的话，就叫我懒惰吧，但这和我愿意检查的一样多，至少没有关于我在寻找什么样的问题的指导，至少也有合理的保证，这是我寻找的合适的地方。如果您展示了可以插入几个节点并获得预期的结构，那么就会有帮助(例如)，然后显示删除节点时出错的地方。节点还在吗？其他节点会丢失吗？所有的节点都是正确的，但是平衡是错误的吗？如果是的话，天平有什么问题？