向AVL树插入元素时触发double free错误导致Core Dump

问题场景 #

实现了AVL搜索树模板类，向空树插入元素时触发以下错误：

free(): double free detected in tcache 2
Aborted (core dumped)

插入逻辑仅执行了空节点创建的代码块：

if (t == NULL)
{
    t = new Node(k, v);
}

错误原因 #

1. 局部变量生命周期不匹配：main函数中WordItem item是栈上的局部变量，作用域仅限于if代码块内部。代码块执行完毕后，栈上的item会被系统自动销毁。
2. 非法指针操作：将栈对象的地址&item传入树的insert方法，树的节点保存了这个指针。程序结束时，树的析构函数调用makeEmpty，其中delete t->value尝试释放栈对象的内存（这本身就是未定义行为），同时栈对象会被系统二次释放，最终触发双重释放错误。

修复方案 #

1. 动态分配WordItem对象 #

将栈上的局部对象改为堆上动态分配，确保对象生命周期由树管理：

int main()
{
    AVLSearchTree<string, WordItem *> myTree;
    
    string s = "someword";
    string filename = "a.txt";
    if(!myTree.doesExist(s))
    {
        int initToOne = 1;
        // 用new创建堆对象，树的析构函数可安全释放
        WordItem* item = new WordItem(s, filename, initToOne);
        myTree.insert(s, item);
    }
    
    return 0;
}

2. 优化树的方法安全性 #

• 修改doesExist的参数为const Key&，避免不必要的拷贝，同时支持常量键查询：

  bool doesExist(const Key& key)
  {
      return find(key, root) != NULL;
  }
  

• 为getWordItem添加空指针检查，避免访问不存在的节点：

  Value& getWordItem(const Key& key)
  {
      Node* node = find(key, root);
      if (node == nullptr) {
          throw std::runtime_error("指定的键不存在");
      }
      return node->value;
  }
  

3. 验证内存释放逻辑 #

确保makeEmpty中的delete t->value仅作用于堆上分配的对象，避免释放栈内存或重复释放。

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