Trie 字典树

1. Trie 字典树的基础知识

（1）什么是字典树

Trie 字典树是一种基于字符串集合构造的有根树，具有如下特点： - 利用字符串的公共前缀，有效节约存储空间。 - 常用于 统计、排序和保存大量字符串，比如文本词频统计、搜索引擎优化等场景。

优点： - 利用公共前缀减少查询时间，避免无谓的字符串比较。 - 查询效率高于哈希树。

基本性质： 1. 根结点不包含字符，除根结点外每个结点只包含一个字符。 2. 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。 3. 每个结点的所有子结点包含的字符都不相同。

（2）字典树的时间复杂度和空间复杂度

• 时间复杂度：
• 构建字典树：$O(n)$，其中 $n$ 为所有字符串长度之和。

• 查找字符串：$O(k)$，其中 $k$ 为查找字符串的长度。

• 空间复杂度：

• 每个结点需要用一个数组存储子结点的指针，即使子结点很少，也需要一个完整大小的数组。
• 假设总字符集大小为 $26$（小写字母），字符串总长度为 $10^5$，则空间复杂度为 $10^5 \times 26$。

2. Trie 树的构造与查询

Trie 树的示例结构

以下为一个包含多个字符串的 Trie 树示意图：

假设我们插入以下字符串到 Trie 树中：["cat", "car", "cart", "dog", "dot"]

    (root)
     /  \
    c    d
   /      \
  a         o
 / \       / \
t*   r*   g*  t*
    /   
   t*

（*表示单词结尾）

Trie 树的构造步骤

1. 插入字符串 "cat"
2. 从根节点开始，插入 'c' -> 'a' -> 't'。
3. 插入字符串 "car"
4. 从根节点开始，'c' 和 'a' 已经存在，继续插入 'r'。
5. 插入字符串 "cart"
6. 从根节点开始，'c' -> 'a' -> 'r' 已经存在，继续插入 't'。
7. 插入字符串 "dog"
8. 从根节点开始，插入 'd' -> 'o' -> 'g'。
9. 插入字符串 "dot"
10. 从根节点开始，'d' -> 'o' 已经存在，继续插入 't'。

查询操作

查询字符串 "cat"

• 路径：'c' -> 'a' -> 't'
• 结果：找到 "cat"。

查询字符串 "cart"

• 路径：'c' -> 'a' -> 'r' -> 't'
• 结果：找到 "cart"。

查询字符串 "dog"

• 路径：'d' -> 'o' -> 'g'
• 结果：找到 "dog"。

查询字符串 "cab"

• 路径：'c' -> 'a' -> 'b'（无法继续）
• 结果：未找到 "cab"。

Trie 树的 C++ 实现

const int N = 100010; // 最大节点数，根据数据规模调整
int son[N][26]; // Trie 树的子节点数组
int cnt[N];     // 记录以某节点为结尾的单词个数
int idx;        // Trie 树当前节点的索引

// 插入单词到 Trie 树
void insert(const char str[]) {
    int p = 0; // 从根节点开始
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a'; // 计算当前字符的编号（0-25）
        if (!son[p][u]) son[p][u] = ++idx; // 如果子节点不存在，创建新节点
        p = son[p][u]; // 移动到子节点
    }
    cnt[p]++; // 单词以当前节点结尾，计数增加
}

// 查询单词在 Trie 树中出现的次数
int query(const char str[]) {
    int p = 0; // 从根节点开始
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a'; // 计算当前字符的编号（0-25）
        if (!son[p][u]) return 0; // 如果子节点不存在，返回 0
        p = son[p][u]; // 移动到子节点
    }
    return cnt[p]; // 返回以当前节点为结尾的单词个数
}

关键点总结

1. 构造：插入每个字符串时，按照字符逐层创建节点，最后标记字符串结束。
2. 查询：逐字符匹配，若找到最后一个字符且标记为结束点，则表示字符串存在。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com