1.简介
字典树（Trie）又名前缀树或单词查找树，最初是由美国计算机科学家Edward Fredkin在1960年提出的。
字典树是一种基于字符串序列的树形结构，可以高效地存储和检索字符串集合中的所有字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
字典树的优点是利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
字典树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
2.性质
（1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
（2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符都不相同。
（4）由于每个节点都是一个字符串的前缀，因此在字典树中任意两个不同字符串的路径都不会相交。
一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
3.示例
假设有 b，abc，abd，bcd，abcd，efg，hii 这 6 个单词，那我们创建trie树就得到那么字典树长下面这个样子。
Trie 可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。
Trie 通常用于表示字符串，但也可以表示其他的数据。Trie 可以很容易地修改为处理其它结构的有序序列而不仅限于字符串，比如一串数字或形状的排列，比如 bitwise trie，可以用于表示整数或内存地址。
4.用途
字典树可以被广泛应用于字符串检索和匹配问题，比如：
- 实现字符串自动补全和纠错功能。
- 在搜索引擎中实现关键词提示。
- 统计和查找文本中的特定单词或短语出现的次数。
- 在数据压缩领域中，实现基于前缀编码的数据压缩。
5.操作
插入
向字典树中插入一个字符串的过程如下：
- 从根节点开始，依次取出要插入字符串中的每个字符。
- 对于每个字符，在当前节点的子节点中查找是否存在该字符。
- 如果不存在，则创建一个新节点，并将该字符添加为当前节点的子节点。
- 如果存在，则将当前节点移动到该字符对应的子节点，并继续查找下一个字符。
- 最后，在字符串的最后一个字符所对应的节点上，设置一个标记，表示该节点代表一个字符串的结尾。
删除
字典树的删除操作相对于插入和查找操作要稍微复杂一些，因为删除一个字符串不仅要删除该字符串的所有字符节点，还需要删除所有该字符串节点的祖先节点中不再代表其他字符串的节点，以维持字典树的结构性质。
下面是字典树的删除操作步骤：
- 从根节点开始，依次取出要删除的字符串中的每个字符，搜索到该字符串最后一个字符所在的节点。
- 删除该节点上的标记位（如果存在），表示该节点不再代表一个完整的字符串。
- 从该节点开始，向其祖先节点遍历，并检查每个节点是否可以删除。如果该节点是一个字符串节点，或者该节点有其他子节点，则该节点不能删除，遍历结束。
- 如果该节点不是一个字符串节点，且其没有其他子节点，可以将该节点从其父节点的子节点列表中删除，并继续向上遍历父节点。
- 重复步骤3和4，直到所有需要删除的节点都被删除或者遍历到根节点为止。
需要注意的是，字典树的删除操作有可能会导致一些无用的节点残留在树中，因此为了维持字典树的空间效率，我们可以在插入和删除操作时对树进行压缩，即如果一个节点没有其他子节点，并且其父节点也没有其他子节点，则将该节点和其父节点合并成一个节点，从而减少树的深度和节点数量。
查找
从字典树中查找一个字符串的过程如下：
- 从根节点开始，依次取出要查找字符串中的每个字符。
- 对于每个字符，在当前节点的子节点中查找是否存在该字符。
- 如果不存在，则说明要查找的字符串不存在于字典树中，返回失败。
- 如果存在，则将当前节点移动到该字符对应的子节点，并继续查找下一个字符。
- 在字符串的最后一个字符所对应的节点上，检查是否设置了标记，如果设置了，则说明要查找的字符串存在于字典树中，返回成功；否则，说明该节点代表的是某个前缀而不是一个完整的字符串，返回失败。
字典树没有专门的更新操作，因为更新操作可以看作是删除和插入操作的结合。具体地说，如果要更新一个字符串，可以先将该字符串从字典树中删除，然后再将更新后的字符串插入到字典树中。这样就完成了对该字符串的更新操作。
6.实现示例
接下来通过案例来介绍字典树的具体操作。
题目：给你 100000 个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
如果我们使用一般的方法，没查询一个单词都去遍历一遍，那么时间复杂度将为 O(n^2)，这对于 100000 这么大的数据是不能够接受的。假如我们要查找单词 student。那我们通过前缀树只需要查找 s 开头的即可，然后接下来查询 t 开头的即可，对于大量的数据可以省去不小的时间。
下面以 Java 为例，给出简单的实现示例。
树结构
其中 count 表示以当前单词结尾的单词数量。prefix 表示以该处节点之前的字符串为前缀的单词数量。
public class TrieNode {
int count;
int prefix;
TrieNode[] nextNode=new TrieNode[26];
public TrieNode(){
count=0;
prefix=0;
}
}
创建树
//插入一个新单词
public static void insert(TrieNode root,String str){
if(root==null||str.length()==0){
return;
}
char[] c=str.toCharArray();
for(int i=0;i<str.length();i++){
//如果该分支不存在，创建一个新节点
if(root.nextNode[c[i]-'a']==null){
root.nextNode[c[i]-'a']=new TrieNode();
}
root=root.nextNode[c[i]-'a'];
root.prefix++;//注意，应该加在后面
}
//以该节点结尾的单词数+1
root.count++;
}
查询单词或前缀的数量
//查找该单词是否存在，如果存在返回数量，不存在返回-1
public static int search(TrieNode root,String str){
if(root==null||str.length()==0){
return -1;
}
char[] c=str.toCharArray();
for(int i=0;i<str.length();i++){
//如果该分支不存在，表名该单词不存在
if(root.nextNode[c[i]-'a']==null){
return -1;
}
//如果存在，则继续向下遍历
root=root.nextNode[c[i]-'a'];
}
//如果count==0,也说明该单词不存在
if(root.count==0){
return -1;
}
return root.count;
}
//查询以str为前缀的单词数量
public static int searchPrefix(TrieNode root,String str){
if(root==null||str.length()==0){
return -1;
}
char[] c=str.toCharArray();
for(int i=0;i<str.length();i++){
//如果该分支不存在，表名该单词不存在
if(root.nextNode[c[i]-'a']==null){
return -1;
}
//如果存在，则继续向下遍历
root=root.nextNode[c[i]-'a'];
}
return root.prefix;
}
在主函数中测试
class Main {
public static void main(String[] args) {
TrieNode newNode=new TrieNode();
TrieNode.insert(newNode,"hello");
TrieNode.insert(newNode,"hello");
TrieNode.insert(newNode,"hello");
TrieNode.insert(newNode,"helloworld");
System.out.println(TrieNode.search(newNode,"hello"));
System.out.println(TrieNode.searchPrefix(newNode,"he"));
}
}
运行输出：
3
4
7.小结
字典树是一种高效地存储和检索字符串集合中的所有字符串的数据结构。它的主要性质包括从根节点到某个节点路径上的字符连接起来即为该节点所表示的字符串，每个节点的所有子节点所表示的字符串都不相同，以及字典树中的每个节点都可以代表一个字符串。
字典树可以被广泛应用于字符串检索和匹配问题，并且它支持插入、删除和查找三种基本操作。
参考文献
OpenAI ChatGPT
Trie - Wikipedia
数据结构与算法：字典树（前缀树） - 知乎专栏
前缀树(Trie Tree) - | Java 全栈知识体系