1

Здравствуйте. Есть код на СИ, реализующий бинарное дерево. И вот в этом коде упорно косячит метод удаления узла из дерева. Причем я не могу понять, где конкретно, потому что это может случиться и после 500 удалений, и после 1000. Помогите, пожалуйста, найти ошибку. Код ниже.

    typedef struct binaryTreeItem
{
    //char *key;
    keyType key;
    int value;
    struct binaryTreeItem *left;
    struct binaryTreeItem *right;
    struct binaryTreeItem *parent;
} BinaryTreeItem;
#define BINARYTREE_ITEM_SIZE sizeof(BinaryTreeItem)

static BinaryTreeItem *BinaryTree;

void AddBinaryTreeItem(keyType key, int value)
{
    BinaryTreeItem *current, *newBinaryTreeItem;

    newBinaryTreeItem = (BinaryTreeItem*) mm_alloc(BINARYTREE_ITEM_SIZE);
    newBinaryTreeItem->key = key;
    newBinaryTreeItem->value = value;

    if(BinaryTree!=NULL)
    {
        current=BinaryTree;
        while(1)
        {
            if(key < current->key)
            {
                if(current->left!=NULL)
                    current=current->left;
                else
                {
                    newBinaryTreeItem->parent = current;
                    current->left = newBinaryTreeItem;
                    break;
                }
            }
            else if(key > current->key)
            {
                if(current->right!=NULL)
                    current=current->right;
                else
                {
                    newBinaryTreeItem->parent = current;
                    current->right = newBinaryTreeItem;
                    break;
                }
            }
            else
                break;
        }
    }
    else
        BinaryTree = newBinaryTreeItem;
}

BinaryTreeItem *find_node(keyType key)
{
    BinaryTreeItem *current=BinaryTree;
    while(current!=NULL)
    {
        if(key<current->key)
            current=current->left;
        else if(key>current->key)
            current=current->right;
        else
            return current;
    }
    return NULL;
}

int* GetBinaryTreeValueByKey(keyType key)
{
    BinaryTreeItem *p;
    p = find_node(key);
    if(p==NULL)return NULL;
    return &p->value;
}

BinaryTreeItem *get_successor(BinaryTreeItem *node)
{
    BinaryTreeItem *current;
    if(node==NULL)
        return NULL;
    if(node->right!=NULL)
    {
        for(current=node->right;;current=current->left)
            if(current->left==NULL)
                return current;
    }
    else
    {
        for(current=node;current->parent!=NULL;current=current->parent)
            if(current==current->parent->left)
                return current->parent;
        return NULL;
    }
}

void Remove(BinaryTreeItem *node)
{
    BinaryTreeItem *succesor;
    if(node==NULL)
        return;
    if(node->left!=NULL&&node->right!=NULL)
    {
        succesor=get_successor(node);
        node->key=succesor->key;
        node->value=succesor->value;
        Remove(succesor);
    }
    else if(node->left!=NULL)
    {
        node->left->parent=node->parent;
        if(node==node->parent->left)
            node->parent->left=node->left;
        else
            node->parent->right=node->left;
        mm_free((char*)node);
    }
    else if(node->right!=NULL)
    {
        node->right->parent=node->parent;
        if(node==node->parent->right)
            node->parent->right=node->right;
        else
            node->parent->left=node->right;
        mm_free((char*)node);
    }
    else
    {
        if(node->parent->left==node)
            node->parent->left=NULL;
        else
            node->parent->right=NULL;
        mm_free((char*)node);
    }
}

void DeleteBinaryTreeItem(keyType key)
{
    BinaryTreeItem *node;
    node = find_node(key);
    Remove(node);
}
6
  • @hdimon, для начала я что-то не пойму, как у вас одинокий корень удалиться? IMHO parent, left и right у него NULL, и тогда в Remove() if(node->parent->left==node) сразу уронет программу. Или я что-то недосмотрел? (mm_alloc() не нашел).
    – avp
    18 апр 2013 в 6:51
  • Возможно, Вы правы, но понимаете, падает она, когда у нее около 10 тысяч узлов. У меня уже несколько реализаций разных, и все равно падает. Так что проблему одинокого узла я бы пофиксил, но дело не в ней.
    – hdimon
    18 апр 2013 в 7:33
  • @hdimon, а в отладчике в месте падения не смотрели? Вообще, я как-то не понимаю идею с get_succesor() и его рекурсивным удалением. IMHO здесь (случай, когда у удаляемого узла есть оба поддерева) можно проще. Ищете самый левый (это минимальный) лист в правом поддереве. Цепляете левое поддерево к его left. Цепляете правое поддерево удаляемого узла к родителю (Вот тут возникает вопрос с удалением корня. Им можно сделать этот самый, только что найденный лист). Удаляете узел. IMHO как-то так. -- Правда остается вопрос, а зачем вообще нужно программировать несбалансированное дерево?
    – avp
    18 апр 2013 в 7:53
  • 1
    @hdimon, оставьте. Я лучше преобразую Ваш комментарий о mm_alloc() в ответ. А с корнем разберитесь, и о балансировке задумайтесь. Хотя, если задача такая, что ключи случайны, то без нее проще.
    – avp
    18 апр 2013 в 8:12
  • 1
    @avp , спасибо Вам большое. С корнем я разобрался, просто взял другой алгоритм удаления узла, для которого даже parent не нужен. Я его сначала написал, потом, когда увидел, что не работает, начал пробовать другие. А они тоже не работали:). Вот и скопировал сюда тот, что поменьше. Насчет балансировки - да, условия таковы, что данные перемешаны практически равномерно, поэтому особого смысла перестраивать дерево нет. Да, и рекурсии в первой версии алгоритма, которую я сейчас и оставил, у меня нигде нет - медленно.
    – hdimon
    18 апр 2013 в 8:17

1 ответ 1

2

Вот только плюнул на все, и коли все равно потерял около 7 часов на это, сделал дерево на 10 узлов, запустил функцию, взял бумажку, перерисовал дерево, и смотрел пошагово, что же с ним происходит. К счастью, я нашел, в чем "ошибка". Мой пример может быть хорошим уроком другим лошпендам, как я, что пренебрег некоторыми свойствами языка.

mm_alloc() - функция планировщика памяти, который выделяет блоки нужного размера. mm_free освобождает блок. Рано или поздно выделяется блок, который ранее уже был выделен. А при создании узла я не делаю newBinaryTreeItem->right(left) = NULL. Думаю, понимаете, что происходит дальше :).

1
  • Лучше в подобных случаях просто обнулять весь отдаваемый из аллокатора блок.
    – avp
    18 апр 2013 в 8:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.