1

我在网上找到了一些红黑树的代码，并正在尝试实现它。

我不想使用assert原始代码位于此处的函数

n->color = child->color;在删除修复之前，我在线路上遇到了段错误。调试后发现本例中不存在child，原来代码中assert语句的原因也是如此。我决定添加我认为合适的附加 if 子句，围绕从 child 向下处理的所有内容。

但是，现在程序实际上并没有删除，因为如果孩子不存在，它永远不会进入循环。经过反复试验，我仍然找不到关闭 if 子句以正确代替 assert 语句的位置。

请让我知道你的想法！

这是我的“翻译”代码，没有断言，而是使用 if 语句。

void delete_node(int key)
{
    node* child;
    node* n ;

   n = searchTree(key);

    if(n == NULL)return;

    if(n->left != NULL && n->right != NULL)
    {
        node* pred = n->left;
        while(pred->right != NULL)
            pred = pred->right;

        n->value = pred->value;
        n = pred;
    }
if(n->right != NULL || n->left != NULL){

    child = n->right == NULL ? n->left : n->right;
    if(n->color == 'b')
    {
        n->color = child->color;
        delete_fix1(n);
    }

    swap_nodes(n, child);
    if(n->parent == NULL && child != NULL)
        child->color = 'b';
    free(n);

}

}

测试数据（尝试删除时发生 Seg Fault 4）：i 代表插入（据我所知，插入完美无缺） d 代表删除

i 7
i 8
i 1
d 8
i 4
i 10
d 4
i 11
4

1 回答 1

1

这：

assert(n->left == NULL || n->right == NULL)

远不及这个：

if (n->right != NULL || n->left != NULL)

重新检查您的翻译。断言声明其中之一必须为 NULL。如果其中一个不为NULL，则您的 if-expr 评估为 true 。如果两者都不为空，则您的 if-expr 通过，断言将失败。同样，如果两者都为 NULL，则 if-expr 失败，而断言会通过。

做这种事情时不要走捷径。第一的。无论您添加了多少检查，都保留断言。其次，在它启动并工作之前，逐字复制您的 if (expr): 或 (!(expr)) 中的断言子句以获取救助条件。

逐字检查：

assert(n->left == NULL || n->right == NULL)
if (n->left == NULL || n->right == NULL)...

救助检查：

assert(n->left == NULL || n->right == NULL)
if (!(n->left == NULL || n->right == NULL))
    bailout loud.

使用集成的 if-expr编辑链接代码的翻译

void rbtree_delete(rbtree t, void* key, compare_func compare)
{
    node child;
    node n = lookup_node(t, key, compare);
    if (n == NULL) return;  /* Key not found, do nothing */
    if (n->left != NULL && n->right != NULL) {
        /* Copy key/value from predecessor and then delete it instead */
        node pred = maximum_node(n->left);
        n->key   = pred->key;
        n->value = pred->value;
        n = pred;
    }

    assert(n->left == NULL || n->right == NULL);
    if (n->left == NULL || n->right == NULL) // << note: SAME as above
    {
        child = n->right == NULL ? n->left  : n->right;
        if (node_color(n) == BLACK) {
            n->color = node_color(child);
            delete_case1(t, n);
        }
        replace_node(t, n, child);
        if (n->parent == NULL && child != NULL)
            child->color = BLACK;
        free(n);
    }

    verify_properties(t);
}
于 2012-11-29T04:47:49.047 回答