Red Black Tree - удаление

Question

Я реализовал функцию удаления для RBT (на основе Cormen), похоже, она работает, но проверка на удаление + печать дерева в предзаказе дает мне неправильный ответ.Я потратил несколько часов на поиск того, что может быть не так, но ничего не смог найти ...

Вот функция печати дерева в предзаказе:

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

По крайней мере, IMO, ваш 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);
   }
}

Как есть, это предварительный заказ;post-order или inorder - это просто вопрос перестановки print_data по сравнению с рекурсивными вызовами на print_out (для post-order он идет после них, для inorder между ними). ​​

В частности, однакоprint_out не должен иметь что-либо , имеющее отношение к левому или правому поддереву, за исключением передачи их в качестве параметров в рекурсивном вызове.Он также обычно не должен проверять, являются ли они NIL / NULL, - он должен просто сделать рекурсивный вызов и позволить обработчику if (current_node != NIL) в рекурсивном вызове иметь дело с возможностью того, что мы достигли конечного узла.

Называйте меня ленивым, если хотите, но это примерно столько, сколько я готов исследовать, по крайней мере, без некоторых указаний о том, какую проблему я ищу, и, по крайней мере, какразумная уверенность, что это правильное местоБыло бы полезно (например), если вы показали, что можете вставить несколько узлов и получить ожидаемую структуру, а затем показать , что идет не так, когда вы удаляете узел.Узел все еще там?Другие узлы теряются?Все ли узлы правильные, а баланс неправильный?Если так, что не так с балансом?