TOC
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
字典树的运用其实相当常见，我们在浏览器中输入英文单词的时候，一旦发生错误的单词，就会帮你进行提示，事实上，这个过程就可以利用字典树进行快速的查询实现，与此类似的示例还有搜索建议，提前给你可能需要的搜索内容。
当然，这个过程也可以依赖遍历整个字典实现，但是这样的时间复杂度就是O(n)级别的，而前缀树的查找复杂度可以控制在O(L) L = 搜索内容的长度。
以下是一颗典型的字典树构造
我们可以观察这棵树的细节，该树的每个节点拥有一个label字段，或者叫prefix也行，标记了这个节点所代表的字符，并且每个节点可以拥有多个子节点，代表从该字符开始，往下连结的字符。
所以一个典型的字典树节点大致有三个属性
- label 代表该节点代表的字符
- word 从根节点到该节点的路线能够构成一个单词 存放单词的内容(这里面和图里的做法不太相同，图里的做法其实是吧label和word进行了合并, 两种做法其实都可以，看你需求)
- children 该节点的所有下沿节点
当然在具体的编程之中，你可以灵活的添加自定义属性，对该算法进行改装，进一步提升性能。
字典树大致可以分为两部分，字典树的构建 字典树的查询
字典树的构建
字典树的构建非常简单，大致步骤如下
假设我们拥有一颗字典树，以及一个即将加入字典树的单词 hello
建立两个基本变量
当前节点 curNode 初始值为根节点
当前子字符 curChar 初始值为 hello 中的第一个字符 h
- 找curNode下的节点 是否有节点label等于curChar的 有>进入步骤2 没有>进入步骤3
- 设置curNode 为匹配的node
- 新建一个 label = curChar 的新节点 设置新节点为curNode 如果curChar已经到最后一位 设置node的word为 “hello”
- 让curChar继续向下延续 重复上述步骤 直到curChar处理完毕
字典树的插入过程可以被看作是把需要插入到单词，与我们的树形结构建立对应关系的过程。
字典树的查找
字典的查找事实上步骤和插入其实是完全一致的，也是一个深度优先的遍历过程。
同样是从根节点向下查询，每次向下操作都会让curChar向后延续。
查找会有一些特殊情况
- 如果我们已经到了叶子节点，curChar还没结尾 说明查找肯定失败了
- 如果我们到达了叶子节点 curChar也结束了 但是结尾的label不等于curChar 同样说明失败
- 还没到叶子节点 就发生匹配失败了 同样失败
出现上述的错误情况就可以直接结束循环了。
所以其实正确的情况只有一种，curChar已经结尾，并且当前的节点label == curChar
具体的实现
class ArrayStack<T> {
private ArrayList<T> stack = new ArrayList<T>();
public void push(T ele) {
stack.add(ele);
}
public T pop() {
T ele = stack.get(stack.size() - 1);
stack.remove(stack.size() - 1);
return ele;
}
public Boolean isEmpty() {
return stack.size() <= 0;
}
}
/***
* @deprecated 字典树
* */
class DictTree {
private static class TreeNode {
public ArrayList<TreeNode> children;
public String word = "";
public String prefix = "";
public Boolean isRoot = false;
TreeNode(String prefix, String word) {
this.children = new ArrayList<TreeNode>();
this.word = word;
this.prefix = prefix;
}
}
public TreeNode root;
DictTree() {
this.root = new TreeNode("", "");
this.root.isRoot = true;
}
// 添加一个单词进字典树
public void add(String word) {
ArrayStack<TreeNode> stack = new ArrayStack<TreeNode>();
int wordIndex = 0;
stack.push(this.root);
while (!stack.isEmpty() && wordIndex < word.length()) {
TreeNode node = stack.pop();
String wordItem = word.substring(wordIndex, wordIndex + 1);
TreeNode foundNode = null;
for (TreeNode child : node.children) {
// 找到匹配 直接结束遍历
if (child.prefix.equals(wordItem)) {
foundNode = child;
break;
}
}
// 未找到匹配 手动新建
if (foundNode == null) {
String endWord = wordIndex < (word.length() - 1) ? "" : word;
TreeNode newNode = new TreeNode(wordItem, endWord);
node.children.add(newNode);
foundNode = newNode;
}
wordIndex++;
stack.push(foundNode);
}
}
// 在字典树中进行搜索
public String search(String word) {
ArrayStack<TreeNode> stack = new ArrayStack<TreeNode>();
int wordIndex = 0;
stack.push(this.root);
String result = "404 Not found";
// stack.isEmpty() 代表没有找到能和当前 wordItem 匹配的下一个子节点
// wordIndex < word.length() 代表要搜索的字符已经结尾
while (!stack.isEmpty() && wordIndex < word.length()) {
TreeNode node = stack.pop();
String wordItem = word.substring(wordIndex, wordIndex + 1);
for (TreeNode child : node.children) {
if (child.prefix.equals(wordItem)) {
// 找到匹配 当前字符正好结尾 && node确实是一个单词 && node.word == word
if (wordIndex == word.length() - 1 && child.word.equals(word)) {
result = word;
} else { /* 继续循环 */
stack.push(child);
wordIndex++;
}
}
}
}
return result;
}
}
class Index {
public static void main(String[] args) throws Exception {
DictTree dt = new DictTree();
dt.add("geek");
dt.add("geometry");
println(dt.search("good")); // 404 Not Fount
println(dt.search("geek")); // geek
}
}
总结
字典树是一种典型的利用空间换时间的算法。
字典树可以被用于，字符串检索，词频统计，热门搜索, 字符串排序等用途。