Trie详（？）解

wenmingge · 2025-05-29 19:45:49 · 算法·理论

0.Trie介绍

Trie，即字典树、单词查找树，是一种使用空间换取时间的数据结构。 除了根节点（空字符），其它节点都是一个字符，所以字典树上的一条路径就是一个的字符串。也就是说，字符串共用一个前缀。

1.Trie的结构

以拥有字符串 a、abc、abcd、bnm、brx、lje 的一棵 Trie 为例（红色节点标志着这是一个字符串的最后字符，不然无法确认）： 可以发现 Trie 每个字符串的最后字符在树上离 root 节点即这个字符串的长度。 Trie 的每个节点的儿子也只可能有字符集的大小个，一般来说，这个数不超过 256。 同时，Trie 最差的空间复杂度即 O(\sum M)（M 代表字符串的长度），不难想到构造这样的例子只需要让前缀不同即可。

这里给出数组实现的代码（一样的，后文中我们也只使用数组实现）：

struct TrieNode
{
    bool isend;//是否为字符串结尾
    int son[256];//子节点 
}t[200005];

2.Trie的基本操作

插入

例如我们将上图所示的 Trie 再插入一个字符串 aaa，Trie 就会变成： 操作顺序即：

• 从 root 节点出发，保存一个计数器 cnt，代表当前要插入的字符（插入 S，下标从 1 开始）。
• 寻找当前节点的子节点，若存在等同于 S_{cnt} 的节点，进入这个节点，cnt 加一，继续这个操作直至 cnt=|S|+1；否则进入下一步。
• 插入 S_{cnt}，cnt 加一，进入上一步（实际上已经没有意义，因为必定不存在子节点，故不用查询，但为了实现方便可以这样）。 代码实现为：

  int Cnt=1;
  void insert(char* s)
  {
  int cnt=0,len=strlen(s);
  for(int i=0;s[i];i++)
  {
      if(t[cnt].son[s[i]]==0)t[cnt].son[s[i]]=Cnt++;
      cnt=t[cnt].son[s[i]];
      if(i==len-1)t[cnt].isend=1;
  }
  }

  查询

  以图中 Trie 寻找字符串 bna 为例（箭头为查询顺序）： 操作顺序即：

• 从 root 节点出发，保存一个计数器 cnt，代表当前要查询的字符（插入 S，下标从 1 开始）。
• 寻找当前节点的子节点，若存在等同于 S_{cnt} 的节点，进入这个节点，cnt 加一，继续这个操作直至 cnt=|S|+1，直至 cnt=|S|，寻找当前节点的子节点是否有为最后且等于 S_{cnt} 的字符，没有或不是最后进入下一步；否则进入下一步。
• 字符串不存在。 代码实现为：

  bool find(char* s)
  {
  int cnt=0;
  for(int i=0;s[i];i++)
  {
      if(t[cnt].son[s[i]]==0)return 0;
      cnt=t[cnt].son[s[i]];
  }
  if(t[cnt].isend==0)return 0;
  return 1;
  }

  完整实现

  仅为示例：

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  struct TrieNode
  {
  bool isend;//是否为字符串结尾
  int son[256];//子节点 
  }t[200005];
  int Cnt=1;
  void insert(char* s)
  {
  int cnt=0,len=strlen(s);
  for(int i=0;s[i];i++)
  {
      if(t[cnt].son[s[i]]==0)t[cnt].son[s[i]]=Cnt++;
      cnt=t[cnt].son[s[i]];
      if(i==len-1)t[cnt].isend=1;
  }
  }
  bool find(char* s)
  {
  int cnt=0;
  for(int i=0;s[i];i++)
  {
      if(t[cnt].son[s[i]]==0)return 0;
      cnt=t[cnt].son[s[i]];
  }
  if(t[cnt].isend==0)return 0;
  return 1;
  }
  int q,op;
  char s[200005];
  signed main()
  {
  cin>>q;
  while(q--)
  {
      cin>>op>>s;
      if(op==1)insert(s);
      else
      {
          if(find(s))cout<<"YES"<<endl;
          else cout<<"NO"<<endl;
      }
  }
  return 0;
  }

  时间复杂度

  因为 Trie 的操作只会进入一条路径，故最差时间复杂度为 O(M)（M 为字符串长度）。

  3.例题及对比其它算法或数据结构的比较

  洛谷P8306 【模板】字典树

备注：模板

洛谷P4551 最长异或路径 洛谷P10471 最大异或对 The XOR Largest Pair

备注：01Trie

4.Trie的拓展

由于 Trie 的优越复杂度和树形的易拓展性，Trie 被应用于许多算法。例如 AC 自动机、01Trie 等算法，请读者自行了解。