从 BST 中删除最小节点导致分段错误 C++

Question

我正在尝试从 BST 中删除最小节点。但是我遇到了段错误。

根据我的理解，最小节点将没有子节点，因此删除它不会导致遗弃子树。我不确定如何从 BST 中删除节点，我看到一些使用 free() 而不是 delete 的解决方案。我哪里错了？

代码在 bst.hpp
构造函数从第 23 行开始
插入函数从第 96 行开始
delete_min 函数从第 142 行开始
分钟函数从第 180 行到第 203 行开始

***在编辑中添加了一些代码

void delete_min()
{
    Node* min_node = min();
    Node* min_parent = min_node->parent; //Added this
    
    if(!root)
    {
        return;
    }

    // If min is root (Added this)
    if(!root->left)
    {
        auto tmp = root;
        root = root->right;
        delete tmp;
        return;
    }

    min_parent->left = min_node->right; //Added this
    delete min_node;
    --size;    
}

Node* min()
{
    if(root == nullptr)
    {
        return root;
    }
    else
    {
        return min(root);
    }
}

Node* min(Node* node)
{
    while(node->left != nullptr)
    {
        node = node->left;
    } 
    return node;
}

Answer 1

起初你假设最小节点没有 children 是错误的；它没有左child，但可能有右child；考虑最简单的根节点和一个大于 child 的情况：

  1
   \
    2

然后要删除一个节点，您不能只删除它，还需要调整它的 parent 的左指针 - 或者根指针，如果根是最小节点。您可以简单地将它设置为最小值的右边 child （可以是另一个节点或空指针）。

根据网上GDB提供的code代码更新（此版本与问题中的版本不匹配！）：

Node* min_node = min();
if(min_node->right != nullptr)
{
    min_node->parent->left = min_node->right;
}

delete min_node;

你需要更新parent的左边child 无条件——如果没有grandchild，你就复制这样的空指针，这很好，因为无论如何都不会再有一个正确的 child（唯一的被删除）。

但是如果有一个 grandchild 你需要更新它的 parent（否则它会保持指向已删除的节点，因此会悬空！ ):

Node* min_node = min();
min_node->parent->left = min_node->right;
if(min_node->right)
{
    min_node->right->parent = min_node->parent;
}

delete min_node;

但是，为此，您也需要可用的 parent 节点，因此您需要适当地调整最小值的查找除非您的节点包含 link 到他们各自的 parent，也是。假设情况并非如此，那么您的迭代可能如下所示：

void deleteMin() { // special handling: empty tree if(!root) { return; } // special handling: minimum is root if(!root->left) { auto tmp = root; root = root->right; delete tmp; return; } // now look for the minimum as you had already, but keep // track of the parent node as well! auto parent = root; child = root->left; while(child->left) { parent = child; child = child->left; } // OK, minimum found; essential step: adjust its parent! parent->left = child->right; // works for both a child available or not // now can safely delete: delete child; }

从 BST 中删除最小节点导致分段错误 C++

Deleting minimum node from BST results in segmentation fault C++

c++

segmentation-fault

binary-search-tree