字典树（trie） 算法笔记

P1 字典树是什么

顾名思义就像一个字典一样，可以查询某单词是否出现，也可以查找同一前缀的单词的个数等等操作。

P2 字典树的实现

字典树是用树来实现的（这不废话吗），如果从根节点走到一个已标记过的节点（后面我们会称它为单词节点）的一条路径就是一个单词。
我们定义一下变量（或数组）的表示含义：

• \(tot\): 表示当前一共有多少个节点。
• \(nex[p][c]\): 表示 \(p\) 节点的走 \(c\) 这条路径的下一个节点。
• \(exist[p]\): 表示 \(p\) 是否为单词节点。
• \(deta[p]\): 表示 \(p\) 节点的属性（权值），这个数组可有可无（通常为经过此节点的次数）。

很快我们就可以写出插入字符串，和查询字符串是否存在的代码，代码如下：

void insert(string s, int p = 0) {
  for (int i = 0, c; i < s.size(); i++) {
    c = ToId(s[i]);                      // ToId为字符转整数的函数
    !nex[p][c] && (nex[p][c] = ++tot);   // 若没有此节点，开辟新节点
    p = nex[p][c] /*往下走*/, cnt[p]++;  // 此处cnt为上述的deta，为经过此节点的次数
  }
  exist[p] = 1;  // 将此节点标记为但此节点
}
bool query(string s, int p = 0) {
  for (int i = 0, c; i < s.size(); i++) {
    c = ToId(s[i]);
    if (!nex[p][c]) {
      return 0;
    }               // 没有路了没有此单词
    p = nex[p][c];  // 往下走
  }
  return exist[p];
}  // query的含义可以改变，此处是查询此字符串是否存在

很容易发现这个数据结构是一个用空间来换时间的数据结构，空间复杂度为：\(O(nmt)\)，\(n\) 表示单词的个数，\(m\) 表示单词的长度，\(t\) 表示字符的种类数。