Функция удаления AVL не работает (ошибка сегментации) - PullRequest
Новая
       22

Функция удаления AVL не работает (ошибка сегментации)

0 голосов
/ 23 апреля 2020

Приветствие!

Я пытаюсь создать класс для дерева двоичного поиска AVL. Все в порядке до тех пор, пока я не должен создать для него функцию удаления узла.

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

Когда программа собирается выполнить функцию удаления, происходит сбой.

Я запустил ее через отладчик, и она выдает ошибку сегментации, которую я не могу найти. Я думаю, что из стека вызовов отладчика он, вероятно, находится в одной из этих функций, но я не могу его найти.

Вот код для функций поворота и функции удаления. Я уверен, что это в одном из них, поскольку именно это показывает мне отладчик. Любая помощь будет оценена, спасибо!

Функции вращения: 

AVLnode* AVL::RR_rotation(AVLnode* rootPtr)
{
   AVLnode* temp1 = rootPtr->left;
   AVLnode* temp2 = temp1->right;
   temp1->right = rootPtr;
   rootPtr->left = temp2;
   rootPtr->height = maxH(Height(rootPtr->left), Height(rootPtr->right)) + 1;
   temp1->height = maxH(Height(temp1->left), Height(temp1->right)) + 1;
   return temp1;
}

AVLnode* AVL::LL_rotation(AVLnode* rootPtr)
{
    AVLnode* temp1 = rootPtr->right;
    AVLnode* temp2 = temp1->left;
    temp1->left = rootPtr;
    rootPtr->right = temp2;
    rootPtr->height = maxH(Height(rootPtr->left), Height(rootPtr->right)) + 1;
    temp1->height = maxH(Height(temp1->left), Height(temp1->right)) + 1;
    return temp1;
}

AVLnode* AVL::LR_rotation(AVLnode* rootPtr)
{
   AVLnode* temp;
   temp = rootPtr->left;
   rootPtr->left = RR_rotation(temp);
   return LL_rotation(rootPtr);
}

AVLnode* AVL::RL_rotation(AVLnode* rootPtr) 
{
   AVLnode* temp;
   temp = rootPtr->right;
   rootPtr->right = LL_rotation(temp);
   return RR_rotation(rootPtr);
}

А вот функция удаления: 

AVLnode* AVL::Delete(AVLnode* rootPtr, std::string word)
{
    if (rootPtr == nullptr)
    {
        return rootPtr;
    }
    if (word < rootPtr->word )
    {
        rootPtr->left = Delete(rootPtr->left, word);
    }
    else if(word > rootPtr->word )
    {
        root->right = Delete(rootPtr->right, word);
    }
    else
    {
        if (rootPtr->amount > 1)
        {
            rootPtr->amount = rootPtr->amount - 1;
        }
        else
        {
            if ((rootPtr->left == nullptr) && (rootPtr->right == nullptr))
            {
                AVLnode* temp = rootPtr;
                delete temp;
                rootPtr = nullptr;
            }
            else if (rootPtr->left == nullptr)
            {
                AVLnode* temp = rootPtr;
                delete temp;
                rootPtr = rootPtr->right;
            }
            else if (rootPtr->right == nullptr)
            {
                AVLnode* temp = rootPtr;
                delete temp;
                rootPtr = rootPtr->left;
            }
            else
            {
                AVLnode* temp = FindMin(rootPtr->right);
                rootPtr->word = temp->word;
                rootPtr->right = Delete(rootPtr->right, temp->word);
            }
        }
    }
    rootPtr->height = 1 + maxH(Height(rootPtr->left),  Height(rootPtr->right));
    int balance = getBalance(rootPtr);
    if ((balance > 1) && (getBalance(rootPtr->left) >= 0))
    {
        return RR_rotation(rootPtr);
    }
    if ((balance > 1) &&  (getBalance(rootPtr->left) < 0))
    {
        return LR_rotation(rootPtr);
    }
    if ((balance < -1) && (getBalance(rootPtr->right) <= 0))
    {
        return RR_rotation(rootPtr);
    }
    if ((balance < -1) && (getBalance(rootPtr->right) > 0))
    {
        return RL_rotation(rootPtr);
    }
  return rootPtr;
}

1 Ответ

2 голосов
/ 23 апреля 2020

Я заметил, по крайней мере, пару моментов, которые могут привести к проблеме: 

        AVLnode* temp = rootPtr;
        delete temp;
        rootPtr = rootPtr->right;

здесь вы удалили область памяти, на которую указывает rootPtr. Следовательно, все, что указывал rootPtr, теперь также выпущено, и вы не должны обращаться к нему.

Одна безопасная альтернатива: 

        else if (rootPtr->left == nullptr)
        {
            AVLnode* temp = rootPtr->right;
            delete rootPtr;
            rootPtr = temp;
        }
        else if (rootPtr->right == nullptr)
        {
            AVLnode* temp = rootPtr->left;
            delete rootPtr;
            rootPtr = temp;
        }
...