删除二叉搜索树（BST）根节点引发double free()错误排查

问题背景 #

我用C++实现了带父指针的二叉搜索树（BST），节点定义如下：

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

树类单独实现了插入、平衡、搜索及删除节点功能，目前旋转、平衡、插入和访问功能均验证正常。但在实现仅处理叶子节点的remove函数时，删除非根叶子节点功能正常，删除作为叶子的根节点（无论之前是否有子节点）时，程序退出会触发double free();错误。

当前remove函数代码：

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

问题原因 #

double free()错误的核心是同一内存块被重复释放。删除根叶子节点时，你只执行了delete delnode;，但树类中必然持有一个指向根节点的成员变量（比如root），删除后这个变量没有被置为NULL。后续程序退出时，树的析构函数会再次尝试释放这个已经被删除的根指针，导致重复释放内存。

修复方案 #

修改删除根叶子节点的分支，在delete之后将树的根节点指针置空：

//The node is both root and leaf
if (!parent) {
  delete delnode;
  this->root = nullptr; // 替换成你树类中根节点成员的实际变量名
  return;
};

额外验证点 #

• 检查树的析构函数逻辑：如果析构函数会遍历节点释放或直接释放根指针，必须确保根指针在删除后被正确置空，避免野指针。
• 确认select函数返回的节点指针没有被其他地方非法持有，防止后续误操作野指针。

内容的提问来源于stack exchange，提问作者RGBCoco