AVL删除功能不工作（分段错误）。

Question

您好！我正在尝试构建一个AVL二进制搜索树的类。

我正试图构建一个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;
}

Answer 1

我发现至少有几个点可能会导致这个问题。

        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;
        }