Trie - tenji/ks GitHub Wiki
字典树
一、什么是字典树？
字典树，是一种空间换时间的数据结构，又称 Trie 树、前缀树，是一种树形结构（字典树是一种数据结构），典型用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
可能大部分情况你很难直观或者有接触的体验，可能对前缀这个玩意没啥概念，可能做题遇到前缀问题也是暴力匹配蒙混过关，如果字符串比较少使用哈希表等结构可能也能蒙混过关，但如果字符串比较长、相同前缀较多那么使用字典树可以大大减少内存的使用和效率。一个字典树的应用场景：在搜索框输入部分单词下面会有一些神关联的搜索内容，你有时候都很神奇是怎么做到的，这其实就是字典树的一个思想。
字典树可以最大限度地减少无谓的字符串比较，用于词频统计和大量字符串排序。自带排序功能，使用中序遍历序列即可得到排序序列。但是如果字符很多相同前缀很少的话那字典树就没啥效率优势的（因为要一个一个访问节点）。
字典树的真实应用有很多，例如字符串检索、文本预测、自动完成，see also，拼写检查、词频统计、排序、字符串最长公共前缀、字符串搜索的前缀匹配、作为其他数据结构和算法的辅助结构等等，这里就不再介绍啦。
二、字典树的特性
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
三、设计实现字典树
3.1 类结构
class TrieNode {
Map<Character, TrieNode> sonMap;
boolean isEnd;
public TrieNode() {
sonMap = new HashMap<>();
}
}
3.2 插入
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(!node.sonMap.containsKey(ch)) {
// 不存在则插入
node.sonMap.put(ch, new TrieNode());
}
node = node.sonMap.get(ch);
}
node.isEnd = true;
}
3.3 查询
public boolean search(String word) {
TrieNode node = root;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(!node.sonMap.containsKey(ch)) {
return false;
}
node = node.sonMap.get(ch);
}
// 必须标记为 true 证明有该字符串
return node.isEnd == true;
}
3.4 前缀查找
public boolean startsWith(String prefix) {
TrieNode node = root;
for(int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if(!node.sonMap.containsKey(ch))
{
return false;
}
node = node.sonMap.get(ch);
}
// 执行到最后一步即说明满足条件
return true;
}