删除 BST 中的最终节点导致故障

Question

我正在用 C++ 构建一个二叉搜索树，它由包含指向父级的指针、指向左右子级的指针、整数键和模板值的节点组成，如下所示。

template <class T> class Node {
 private:
  Node<T>* parent;
  Node<T>* left;
  Node<T>* right;

  unsigned int key;
  T value;

 public:
  /*constructors, accessors, mutators, rotating functions are here*/

我为树本身提供了一个单独的类，主要用于插入、平衡树、搜索和删除节点。在此类中，删除节点的函数采用一个键并从树中删除该节点。到目前为止，我已经验证了所有旋转、平衡、插入和访问功能都可以正常工作。在创建从树中删除节点的函数时，我在删除根时遇到了一个问题。下面是删除功能。

//This currently is only for deleting leaf nodes
void remove(unsigned int key) {
  //Find the node being deleted
  Node<T>* delnode = this->select(key);
  if (!delnode) { return; };
  
  //If the value is a leaf node
  if (!delnode->getLeft() && !delnode->getRIght()) {
    //Store the parent node
    Node<T>* parent = delnode->getParent();

    //The node is both root and leaf
    if (!parent) {
      delete delnode;
      return;
    };

    //If the node is not a root, clip the parent connection
    if (delnode->getKey() < parent->getKey()) {
      parent->setLeft(NULL);
      delnode->setParent(NULL);
    } else if (delnode->getKey() > parent->getKey()) {
      parent->setRight(NULL);
      delnode->setParent(NULL);
    };

    //Delete the node now
    delete delnode;
    return;
  };
};

可靠导致错误的最小代码部分是上述函数的以下部分。

if (!parent) {
  delete delnode;
  return;
};

据我验证，代码的其他部分可以正常工作，并正确删除叶节点。删除树的根（无论它是否曾经有子树）会导致“double free();”程序退出时出错。

我在之前的代码中找不到会导致使用“delete”抛出“double free();”的错误错误，可能是什么原因？

Answer 1

我为树本身有一个单独的类，...

大概，这个类维护了一个指向树的指针：

template <class T>
class BTree
{
    Node<T>* root;
    // ...
}

函数

remove

删除根节点后，必须将

root

指针设置为

nullptr

。

现在发生的事情是：

1. 在函数remove中，根被删除一次，如

   delnode

   。
2. 在类

   BTree

   的析构函数中被第二次删除。

因此，双重释放错误。