字典树（Trie）

概念讲解

什么是 Trie？

Trie 是一种树形数据结构，用于高效存储和检索字符串。

特点

  • 根节点为空
  • 每条边代表一个字符
  • 从根到节点的路径表示一个字符串

实现

123456789101112131415161718192021222324const int N = 100005;
int trie[N][26];
int cnt[N];  // 以该节点结尾的字符串数量
int idx = 0;

void insert(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }
    cnt[p]++;
}

int query(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!trie[p][u]) return 0;
        p = trie[p][u];
    }
    return cnt[p];
}

01-Trie（最大异或）

12345678910111213141516171819202122void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }
}

int query(int x) {
    int p = 0, ans = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (trie[p][1-u]) {
            ans |= (1 << i);
            p = trie[p][1-u];
        } else {
            p = trie[p][u];
        }
    }
    return ans;
}

考点分析

初赛考查方式

  1. 程序阅读： Trie 操作
  2. 编程题： 字符串匹配

常见考点

  • Trie 构建
  • 字符串匹配
  • 最大异或

练习题

  1. Trie 的时间复杂度是多少？
查看答案

Trie 的时间复杂度：

  • 插入：O(L)O(L)，L 是字符串长度
  • 查询：O(L)O(L)
  • 空间：O(N×L)O(N \times L)，N 是字符串数量
  1. 如何用 Trie 求最大异或？
查看答案

使用 01-Trie：

  1. 将数字按二进制位插入 Trie
  2. 查询时，优先走与当前位相反的路径
  3. 这样可以最大化异或值
12345678910111213int query(int x) {
    int p = 0, ans = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (trie[p][1-u]) {
            ans |= (1 << i);
            p = trie[p][1-u];
        } else {
            p = trie[p][u];
        }
    }
    return ans;
}
  1. Trie 和哈希表的区别？
查看答案
特性 Trie 哈希表
时间复杂度 O(L) O(1) 平均
空间复杂度 O(N×L) O(N)
前缀查询 支持 不支持
有序性 有序 无序

Trie 适合前缀匹配，哈希表适合精确查找。

易错点

⚠️ 注意：

  1. 空间要开够
  2. 01-Trie 要从高位到低位
  3. cnt 记录结尾标记
  4. 注意字符范围