Trie 字典树/前缀树

作者： /

什么是 Trie（前缀树/字典树）

Trie 是一种多叉树字符串结构：从根到叶子节点的路径拼成一个字符串，相同前缀的字符串共享路径。适合前缀匹配、自动补全、敏感词过滤、词频统计等场景。

  • 插入/查询都是 O(L)（L 为字符串长度），与词库规模无关——这是它相对”遍历集合匹配”的核心优势；
  • 空间 O(N·L)，公共前缀越多越省；
  • 节点存：子节点指针 + 结束标记（isEnd）。

C++ 实现（小写字母版）


#include <vector>
#include <string>
using namespace std;

class Trie {
private:
    struct TrieNode {
        vector<TrieNode*> children;
        bool isEnd;
        TrieNode() : children(26, nullptr), isEnd(false) {}
    };
    TrieNode* root;

    TrieNode* findNode(const string& s) {
        TrieNode* node = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }

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 = findNode(word);
        return node && node->isEnd;   // 完整单词才返回 true
    }

    bool startsWith(const string& prefix) {
        return findNode(prefix) != nullptr;  // 只要求前缀路径存在
    }
};

注意 search 与 startsWith 的区别：search("app") 要求 app 是完整单词（isEnd），而 startsWith("app") 只要求前缀路径存在。

通用版（任意字符，哈希表子节点）

仅支持小写字母时用定长数组（快）；字符集不确定或很大时用 unordered_map：


struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};
// insert/search 逻辑同上，只是 children 用 map 查找

扩展：统计前缀出现次数


struct TrieNode {
    int pass = 0;   // 经过该节点的字符串数（前缀计数）
    int end = 0;    // 以该节点结尾的字符串数
    TrieNode* children[26] = {};
};

void insert(const string& word) {
    TrieNode* node = root;
    node->pass++;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) node->children[idx] = new TrieNode();
        node = node->children[idx];
        node->pass++;
    }
    node->end++;
}

int countPrefix(const string& prefix) {
    TrieNode* node = findNode(prefix);
    return node ? node->pass : 0;   // 以 prefix 为前缀的单词数
}

有了 pass/end 计数，countPrefix 就是 O(L) 的——这是”字典树求某前缀出现次数”类题目的标准做法。

删除操作


void remove(const string& word) {
    if (!search(word)) return;
    TrieNode* node = root;
    node->pass--;
    for (char c : word) {
        int idx = c - 'a';
        if (--node->children[idx]->pass == 0) {   // 该路径不再被使用
            delete node->children[idx];
            node->children[idx] = nullptr;
            return;
        }
        node = node->children[idx];
    }
    node->end--;
}

复杂度与应用

  • 时间：插入/查询/删除均 O(L)；空间 O(N·L)；
  • 自动补全：输入前缀快速枚举候选词（DFS 收集子树）；
  • 敏感词过滤：把敏感词建 Trie，扫描文本 O(n)；
  • 词频统计：配合 pass/end 计数；
  • LeetCode 208（实现 Trie）是入门题，进阶可看”单词搜索 II”（Trie + 回溯）。
滚动至顶部