C++实现Trie字典树时的删除操作问题及优化咨询

问题根源 #

你遇到的heap-use-after-free错误，核心原因是erase操作误删除了Trie的root节点。root是整个字典树的入口节点，一旦被释放，后续isPre函数访问root时，就会读取已经被回收的堆内存，触发地址 sanitizer 的报错。

临时方案的合理性 #

你添加“不删除root节点”的条件是完全合理的——root作为Trie的固定入口，除非整个Trie对象被销毁，否则绝不应该被释放。这个方案能直接解决当前的崩溃问题，但可以进一步优化erase逻辑，让整个Trie的实现更健壮。

更优实现建议 #

1. 给节点添加使用计数（count字段） #

为每个Trie节点增加一个count字段，记录有多少字符串的前缀经过该节点。删除时递减计数，只有当计数归0、节点不是root且没有子节点时，才释放该节点。这种设计能避免误删共享前缀的节点，同时确保root永远不会被提前删除。

2. 封装erase逻辑，避免外部直接操作root #

把erase的递归逻辑封装为类的私有辅助函数，外部只需要调用公共的erase(const string& str)方法，不需要传入root，从根源上杜绝误删root的可能。

3. 统一析构清理 #

在Trie的析构函数中递归删除所有节点（包括root），确保对象销毁时不会产生内存泄漏。

改进后的示例代码 #

#include <iostream>
#include <string>
#include <unordered_map>
#include <functional>

using namespace std;

class Trie {
private:
    struct Node {
        bool is_end;       // 标记该节点是否是某个字符串的结尾
        int count;         // 记录经过该节点的字符串数量
        unordered_map<char, Node*> children;

        Node() : is_end(false), count(0) {}
    };

    Node* root;

    // 递归删除辅助函数，返回当前节点是否需要被释放
    bool eraseHelper(Node* node, const string& str, int idx) {
        if (idx == str.size()) {
            // 到达字符串末尾，取消结尾标记
            if (!node->is_end) return false;
            node->is_end = false;
            // 计数减1后，判断是否需要删除当前节点
            return --node->count == 0;
        }

        char c = str[idx];
        if (!node->children.count(c)) return false;

        // 递归处理子节点
        bool shouldDeleteChild = eraseHelper(node->children[c], str, idx + 1);
        if (shouldDeleteChild) {
            delete node->children[c];
            node->children.erase(c);
        }

        // 当前节点是否需要删除：计数归0、不是root、且没有子节点
        return --node->count == 0 && node != root && node->children.empty();
    }

public:
    Trie() : root(new Node()) {}

    // 析构时递归清理所有节点
    ~Trie() {
        function<void(Node*)> destroy = [&](Node* node) {
            for (auto& pair : node->children) {
                destroy(pair.second);
            }
            delete node;
        };
        destroy(root);
    }

    void insert(const string& str) {
        Node* curr = root;
        for (char c : str) {
            if (!curr->children.count(c)) {
                curr->children[c] = new Node();
            }
            curr = curr->children[c];
            curr->count++;
        }
        curr->is_end = true;
    }

    void erase(const string& str) {
        eraseHelper(root, str, 0);
    }

    bool isPre(const string& str, int idx) {
        Node* curr = root;
        for (int i = idx; i < str.size(); ++i) {
            char c = str[i];
            if (!curr->children.count(c)) {
                return false;
            }
            curr = curr->children[c];
        }
        return true;
    }
};

// 测试用例
int main() {
    string str = "a";
    Trie trie;
    cout << trie.isPre(str, 0) << endl; // 输出0（false）
    trie.insert(str);
    cout << trie.isPre(str, 0) << endl; // 输出1（true）
    trie.erase(str);
    cout << trie.isPre(str, 0) << endl; // 输出0（false），无崩溃
    return 0;
}

方案优势 #

• 避免内存错误：root节点仅在Trie对象析构时才被释放，彻底解决heap-use-after-free问题
• 高效处理共享前缀：count字段确保共享前缀的节点不会被误删，适合多字符串共享前缀的场景
• 封装性更强：所有核心逻辑都封装在类内部，外部调用更简单，降低误操作风险

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