【UCB CS 61B SP24】Lecture 28 - Tries 学习笔记

本文介绍并用 Java 实现了用于存储字符串的高效数据结构 Trie，Trie 可以在近乎常数的时间复杂度下进行字符串的插入与查询操作，且效率不受单词的数量影响。

1. Trie 字典树介绍

Trie（前缀树或字典树）是一种树形数据结构，用于高效存储和检索字符串集合中的键。其核心思想是通过共享公共前缀来减少存储开销，支持快速插入、搜索和前缀匹配操作。

Trie 的主要特点如下：

• 高效的查找：查找一个字符串的时间复杂度与字符串长度成正比，也就是 $O(m)$，与存储的单词数量无关。
• 公共前缀共享：相同前缀的字符串共享同一路径，降低冗余存储。
• 适用场景：字典实现、自动补全、拼写检查、前缀匹配等。

2. 实现 Trie 字典树

首先来画个图看看 Trie 如何表示字符串，Trie 中的每个节点表示一个字符，例如下面这棵 Trie 树可以表示 sad、sam、same 等字符串：

但是我们如何表示 aw、sa 这类不存在的字符串呢？因此每个节点还需要用一个变量 isEnd 标记是否为字符串的结尾，例如下面这棵 Trie 树表示我们存储了 6 个字符串分别为 a、awls、sad、sam、sap、same：

虽然与搜索树、哈希表之类的数据结构比起来 Trie 的效率没有惊人的提升（搜索树与哈希表的时间复杂度分别为对数级与近乎常数级），但是 Trie 能做到一些其他数据结构难以实现的功能，我们以下图为例讲解：

• 前缀匹配：例如可以匹配前缀 sa、aw，可以很轻松地找出所有以 sa 开头的字符串，而在其他数据结构上可能以 sa 开头的字符串分散在各处，因此需要遍历完所有字符串才能找到；
• 查找最长前缀：例如查找 sample 的最长前缀，在其他数据结构上我们需要遍历完所有的字符串，对于每个字符串还要逐个遍历字符判断该字符串是否为 sample 的前缀，然后记录下全局的最长前缀，而 Trie 只要沿着节点查到 sam 的时候发现后面只剩一个节点而且不是 p，说明最长的前缀是 sam。

接下来我们来看一下具体实现 Trie 的流程：

• 插入（Insert）：从根节点出发，依次根据字符串中的每个字符寻找（或创建）相应的子节点；遍历完所有字符后，将最后一个节点标记为结束节点。
• 查找（Search）：按照单词中的每个字符逐层遍历，如果某个字符对应的子节点不存在，则说明该单词不存在；遍历结束后，检查最后一个节点是否标记为结束节点，如果是则单词存在，否则不存在。
• 前缀匹配（StartsWith）：与查找类似，但只需判断从根到最后一个字符的路径是否存在，而不关心最后节点是否为完整单词的结束标志。

假设我们处理只有小写字母的单词，那么我们可以让每个节点包含一个大小为 26 的数组来存储所有可能的子节点。但是这样做可能会造成空间的浪费，如果 Trie 树的每一层都只有一个节点，那么每一层的数组中都会有 25 个位置是 null，如下图所示：

我们可以用 Lecture 19 中学到的哈希表来完成字符到子节点的映射来优化这个问题，此处我们直接调用 java.util.HashMap 实现，使用哈希表后的内存空间使用如下：

Java 实现 Trie 代码如下：

package CS61B.Lecture28;import java.util.HashMap;public class Trie {private static class TrieNode {HashMap<Character, TrieNode> children;boolean isEnd;public TrieNode() {children = new HashMap<>();isEnd = false;}}private final TrieNode root;public Trie() {root = new TrieNode();}/** 核心操作：插入，将 word 插入 Trie 中 */public void insert(String word) {TrieNode p = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);p = p.children.computeIfAbsent(c, key -> new TrieNode());}p.isEnd = true;}/** 核心操作：查找，返回完整单词 word 是否存在 */public boolean search(String word) {TrieNode prefix = searchPrefix(word);return prefix != null && prefix.isEnd;}/** 核心操作：前缀匹配，返回前缀 prefix 是否存在 */public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}/** 辅助方法：查找并返回 word 所在的最后一个节点 */private TrieNode searchPrefix(String word) {TrieNode p = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);if (p.children.get(c) == null) return null;p = p.children.get(c);}return p;}/** 测试 */public static void main(String[] args) {Trie trie = new Trie();trie.insert("sad");trie.insert("sam");System.out.println(trie.search("sad"));  // trueSystem.out.println(trie.startsWith("sa"));  // trueSystem.out.println(trie.search("sa"));  // false}
}

注意：在 insert 方法中使用的 computeIfAbsent(key, mappingFunction) 方法是 Java 8 在 Map 接口中引入的一个默认方法，它的主要作用是根据给定的 key 获取其对应的 value，如果该 key 在 Map 中不存在，则使用提供的映射函数（Mapping Function）计算一个新的 value，并将这个 key-value 对存入 Map 中，然后返回计算得到的 value。也就是说等价于下面这种写法：

if (p.children.get(c) == null) p.children.put(c, new TrieNode());
p = p.children.get(c);