摘要

Trie 被称为前缀树，结构类似树，一个节点有多个子节点，那么在搜索路径中就有多条路，也是高效检索的本质。Trie 的检索和字典查找单词的场景非常相似。

Trie 又被称为前缀树或者字典树，常用的场景有网址搜索、字典查询等需要高效率的查询情况。可以思考在字典中查找一个单词的过程（比如 trie），咱们会先找到单词的第一个字母，找到后再找第二个字母，直到找到最后一个字母，Tire 的查找过程就是这样。

Trie 的数据结构，在存储数据的时候（比如 trie），就依次建立了多个索引（字母做索引），通过多个索引获取一个元素，很大的提高了查询效率。也是有多个索引确定一个元素的逻辑，所以在 Trie 中会需要空间存储索引，这是一种空间换取时间的数据结构逻辑。

trie 的结构类似一个树，trie 的结构总结这几点：

每个节点都有多个子节点每个节点都有一个 char 作为 key元素存放在单词最后一个索引 key 的节点中准备

那么根据 trie 中 Node 的结构，可以设计 Node 如下：

private static class Node { // 父节点 Node parent; // 子节点，因为是多个，这里使用 key-value 结构，即 `HashMap` HashMap children; // char 作为 key Character character; // 存放的元素 V value; // 是否是单词的结尾，如果是 true，那么 value 中存在元素 boolean word; // 构造函数 public Node(Node parent) { super(); this.parent = parent; }}

在 Tride 结构中，也需要定义一个根节点，用 size 来记录结构中元素的数量：

public class Trie { private int size; private Node root;}

这里先实现通过一个 key 检索获取 node 的方法，这个方法在后面要实现的代码逻辑中经常使用，这个方法的大致逻辑是将 key 依次拆分为 char 类型字符，从根节点开始循环找到查询路径是 key 的节点，其中出现的节点或者它的子节点是 null，则认为不存在：

private Node node(String key) { keyCheck(key); Node node = root; int len = key.length(); for (int i = 0; i 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 的逻辑大致是：

首先通过 key 找到在 trie 结构中存放元素的位置在该位置上放置要存放的元素

代码实现的逻辑上需要对以下情况做出处理：

key 不可以是非法的；trie 结构是空的，连 root 都没有，那就需要先创建一个 root；向下查找的过程中，如果 node 的子 node 是空，就需要创建；如果 node 中已经存在元素，就覆盖它，并返回覆盖的元素；最后，容易忽略，也是非常重要的点，就是记录元素的 size 一定要加 1。public V add(String key, V value) { keyCheck(key); if (root == null) { root = new Node(null); } Node node = root; int len = key.length(); for (int i = 0; i trie 结构中删除元素，不能是简单的将存放元素的 node 删除掉，或者将 node 的 value 设置为 null 就可以了。在文章开头提到，trie 是一种空间换时间的结构逻辑，那么就要本着节约的原则操作删除，核心逻辑就是将不需要的索引节点给删除掉。

如何定义该索引节点是不需要的呢？这里很直接，就是该节点不存放元素，并且也没有子节点，那么这个节点就是不需要的，可以放心的删除。

删除元素的大致逻辑是：

先找到元素所在 node，如果 node 存在，就继续走下一步；临时保存 value 值，然后处理 node；最重要的，不要忘记把 trie 的 size 减 1。

在删除元素的时候，需要特别注意这几点：

node 没有子 node 的时候，才可以删除 node，若存在子 node，就需要清理 value 为 null，并设置 word 为 true；删除当前 node 前，获取到它的父 node，删除当前 node 后，再判断它的父 node 是否满足第 1 点，一直循环到出现 word 为 true 或者 node 的子节点不为 null。public V remove(String key) { // 找到最后一个节点 Node 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 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 node = node(key); return (node != null && node.word) ? node.value : null;}示例

判断一个字符串的前缀是否存在，在 trie 结构中非常容易实现：

public boolean startsWith(String prefix) { return node(prefix) != null;}总结：Trie 的数据结构检索效率非常高，和字典中查单词场景非常相似，是空间换时间的结构逻辑；对元素的添加、删除等操作都需要先获取节点，然后做处理，不能忘记对 size 的加减处理；word 标识用做判断是否存在元素。