17370845950

Trie树通过共享前缀存储字符串，支持高效插入、查找和前缀匹配，时间复杂度为O(L)，适用于自动补全、拼写检查等场景。

在处理字符串前缀相关问题时，Trie树（字典树）是一种非常高效的数据结构。它通过共享前缀的方式存储字符串集合，能快速完成插入、查找和前缀匹配操作，时间复杂度为 O(L)，其中 L 是字符串长度。

基本原理与结构设计

Trie树的核心思想是将字符串按字符逐层分解，每个节点代表一个字符，从根到某节点的路径构成一个字符串前缀。常见实现方式是使用指针或数组构建多叉树结构。

每个节点包含：

• 子节点指针数组：通常用大小为26的指针数组对应 'a'-'z' 字符（也可用哈希表支持更多字符）
• 标记位 isEnd：表示是否为某个字符串的结尾

示例：插入 "apple" 后，根 → a → p → p → l → e，e 节点的 isEnd 为 true。

C++ 实现代码

以下是一个简洁且高效的 Trie 树实现：

#include 
using namespace std;

class Trie {
private:
    struct TrieNode {
        vector children;
        bool isEnd;

        TrieNode() : children(26, nullptr), isEnd(false) {}
    };

    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入字符串
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    // 查找完整字符串是否存在
    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                return false;
            }
            node = node->children[idx];
        }
        return node->isEnd;
    }

    // 判断是否有指定前缀
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }
};

应用场景与优化建议

Trie树特别适合以下场景：

• 自动补全：输入前缀后快速列出所有匹配词
• 拼写检查：判断单词是否存在于词典中
• IP路由查找：最长前缀匹配
• 统计高频前缀：可在节点中增加计数器字段

提示：若需节省空间，可改用 unordered_map 替代固定数组；对中文等多字节字符，需调整编码处理逻辑。

基本上就这些，Trie树实现不复杂但容易忽略内存释放。实际项目中可结合智能指针管理生命周期，避免泄漏。