20、数据结构与算法 - 基础：Trie（前缀树）
摘要
Trie 被称为前缀树，结构类似树，一个节点有多个子节点，那么在搜索路径中就有多条路，也是高效检索的本质。Trie 的检索和字典查找单词的场景非常相似。
Trie 又被称为前缀树或者字典树，常用的场景有网址搜索、字典查询等需要高效率的查询情况。可以思考在字典中查找一个单词的过程（比如 trie），咱们会先找到单词的第一个字母，找到后再找第二个字母，直到找到最后一个字母，Tire 的查找过程就是这样。
Trie 的数据结构，在存储数据的时候（比如 trie），就依次建立了多个索引（字母做索引），通过多个索引获取一个元素，很大的提高了查询效率。也是有多个索引确定一个元素的逻辑，所以在 Trie 中会需要空间存储索引，这是一种空间换取时间的数据结构逻辑。
trie 的结构类似一个树，trie 的结构总结这几点：
1、 每个节点都有多个子节点；
2、 每个节点都有一个char作为key；
3、 元素存放在单词最后一个索引key的节点中；
准备
那么根据 trie 中 Node 的结构，可以设计 Node 如下：
private static class Node<V> {
// 父节点
Node<V> parent;
// 子节点，因为是多个，这里使用 key-value 结构，即 HashMap
HashMap<Character, Node<V>> children;
// char 作为 key
Character character;
// 存放的元素
V value;
// 是否是单词的结尾，如果是 true，那么 value 中存在元素
boolean word;
// 构造函数
public Node(Node<V> parent) {
super();
this.parent = parent;
}
}
在Tride 结构中，也需要定义一个根节点，用 size 来记录结构中元素的数量：
public class Trie<V> {
private int size;
private Node<V> root;
}
这里先实现通过一个 key 检索获取 node 的方法，这个方法在后面要实现的代码逻辑中经常使用，这个方法的大致逻辑是将 key 依次拆分为 char 类型字符，从根节点开始循环找到查询路径是 key 的节点，其中出现的节点或者它的子节点是 null，则认为不存在：
private Node<V> node(String key) {
keyCheck(key);
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
if (node == null || node.children == null || node.children.isEmpty()) return null;
char c = key.charAt(i);
node = node.children.get(c);
}
return node;
}
keyCheck 方法是检查 key 是否合法，即 key 不能是 null，也不能是空字符，否则查找就没有意义，这里的处理是直接抛出异常：
private void keyCheck(String key) {
if (key == null || key.length() == 0) {
throw new IllegalArgumentException("key must not be empty");
}
}
添加元素
下面就是实现 trie 结构中的重要方法，添加 Node（节点，下面都以 Node 表示节点）。添加 Node 的逻辑大致是：
1、 首先通过key找到在trie结构中存放元素的位置；
2、 在该位置上放置要存放的元素；
代码实现的逻辑上需要对以下情况做出处理：
1、 key不可以是非法的；
2、 trie结构是空的，连root都没有，那就需要先创建一个root；
3、 向下查找的过程中，如果node的子node是空，就需要创建；
4、 如果node中已经存在元素，就覆盖它，并返回覆盖的元素；
5、 最后，容易忽略，也是非常重要的点，就是记录元素的size一定要加1；
public V add(String key, V value) {
keyCheck(key);
if (root == null) {
root = new Node<>(null);
}
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
char c = key.charAt(i);
// 子节点和存放子节点的变量是空的，就创建一下，不好理解，需要多过几遍
boolean emptyChildren = node.children == null;
Node<V> childNode = emptyChildren ? null : node.children.get(c);
if (childNode == null) {
childNode = new Node<>(node);
childNode.character = c;
node.children = emptyChildren ? new HashMap<>() : node.children;
node.children.put(c, childNode);
}
node = childNode;
}
if (node.word) {
// 替换
V oldValue = node.value;
node.value = value;
return oldValue;
}
node.word = true;
node.value = value;
size++;
return null;
}
删除元素
trie 结构中删除元素，不能是简单的将存放元素的 node 删除掉，或者将 node 的 value 设置为 null 就可以了。在文章开头提到，trie 是一种空间换时间的结构逻辑，那么就要本着节约的原则操作删除，核心逻辑就是将不需要的索引节点给删除掉。
如何定义该索引节点是不需要的呢？这里很直接，就是该节点不存放元素，并且也没有子节点，那么这个节点就是不需要的，可以放心的删除。
删除元素的大致逻辑是：
1、 先找到元素所在node，如果node存在，就继续走下一步；
2、 临时保存value值，然后处理node；
3、 最重要的，不要忘记把trie的size减1；
在删除元素的时候，需要特别注意这几点：
1、 node没有子node的时候，才可以删除node，若存在子node，就需要清理value为null，并设置word为true；
2、 删除当前node前，获取到它的父node，删除当前node后，再判断它的父node是否满足第1点，一直循环到出现word为true或者node的子节点不为null；
public V remove(String key) {
// 找到最后一个节点
Node<V> node = node(key);
if (node == null || !node.word) return null;
size --;
V oldValue = node.value;
// 如果还有子节点
if (node.children != null && !node.children.isEmpty()) {
node.word = false;
node.value = null;
return oldValue;
}
// 如果没有子节点
Node<V> parent = null;
while ((parent = node.parent) != null) {
parent.children.remove(node.character);
if (parent.word || !parent.children.isEmpty()) break;
node = parent;
}
return oldValue;
}
获取元素
获取元素的时候，也是需要先通过 key 得到 node，判断 node 是否存在 value，存在才能返回：
public V get(String key) {
Node<V> node = node(key);
return (node != null && node.word) ? node.value : null;
}
示例
判断一个字符串的前缀是否存在，在 trie 结构中非常容易实现：
public boolean startsWith(String prefix) {
return node(prefix) != null;
}
总结：
- Trie 的数据结构检索效率非常高，和字典中查单词场景非常相似，是空间换时间的结构逻辑；
- 对元素的添加、删除等操作都需要先获取节点，然后做处理，不能忘记对 size 的加减处理；
- word 标识用做判断是否存在元素。