数据结构与算法 / 系统课时
字典树
字典树
字典树用于高效保存和查询大量字符串,核心做法是让具有相同前缀的单词共享路径。本课将用一个支持中英文的 Java 17 示例,完成插入、完整单词查询和前缀查询,并说明结束标记为什么不可缺少。
学习目标
- 理解公共前缀共享与节点结束标记
- 实现插入、完整查询和前缀查询
- 分析操作复杂度与主要空间开销
字典树如何组织字符串
字典树又称 Trie。根节点不表示字符,从根到某个节点经过的边共同组成一个前缀。插入 java 与 javascript 时,两者会复用 j → a → v → a,只为后续不同部分创建新节点。

节点通常只需要两类信息:从当前节点出发的子节点映射,以及当前路径是否构成完整单词的 wordEnd 标记。路径存在不代表单词存在,例如插入 javascript 后,jav 是有效前缀,但不是完整单词。
三个核心操作
插入时逐个读取字符单位:子节点不存在就创建,存在就复用;处理完全部字符后,将最终节点标记为单词结尾。
完整查询与前缀查询可以共用路径定位方法。search(word) 要求目标节点存在且 wordEnd 为 true;startsWith(prefix) 只要求路径存在。这样既减少重复代码,也避免把前缀误判为完整单词。
本课使用 Map<Integer, TrieNode> 保存子节点,并通过 String.codePoints() 按 Unicode 代码点遍历。相比直接使用 char,它能正确处理基本多文种平面之外的字符;若业务要求按用户可见字素处理,还需要额外的文本分段规则。
完整可运行示例
import java.util.HashMap;
import java.util.Map;
public class TrieDemo {
private static class TrieNode {
private final Map<Integer, TrieNode> children = new HashMap<>();
private boolean wordEnd;
}
private static class Trie {
private final TrieNode root = new TrieNode();
public void insert(String word) {
requireText(word, "word");
TrieNode current = root;
for (int codePoint : word.codePoints().toArray()) {
// 只在分支缺失时创建节点,已有公共前缀直接复用
current = current.children.computeIfAbsent(
codePoint,
ignored -> new TrieNode()
);
}
current.wordEnd = true;
}
public boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.wordEnd;
}
public boolean startsWith(String prefix) {
return findNode(prefix) != null;
}
private TrieNode findNode(String text) {
requireText(text, "text");
TrieNode current = root;
for (int codePoint : text.codePoints().toArray()) {
current = current.children.get(codePoint);
if (current == null) {
return null;
}
}
return current;
}
private static void requireText(String text, String name) {
if (text == null || text.isEmpty()) {
throw new IllegalArgumentException(name + " 不能为空");
}
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("java");
trie.insert("javascript");
trie.insert("算法");
trie.insert("算法题");
System.out.println("查找 java: " + trie.search("java"));
System.out.println("查找 jav: " + trie.search("jav"));
System.out.println("前缀 jav: " + trie.startsWith("jav"));
System.out.println("查找 算法: " + trie.search("算法"));
System.out.println("前缀 算: " + trie.startsWith("算"));
System.out.println("查找 数据: " + trie.search("数据"));
}
}将代码保存为 TrieDemo.java,在安装 JDK 17 或更高版本的环境中执行:
javac TrieDemo.java
java TrieDemo预期输出:
查找 java: true
查找 jav: false
前缀 jav: true
查找 算法: true
前缀 算: true
查找 数据: falsejav 的路径已经存在,但最终节点没有结束标记,因此完整查询为 false,前缀查询为 true。
复杂度与工程取舍
设输入字符串含 L 个代码点。在哈希映射平均常数时间访问的前提下,插入、完整查询和前缀查询均为 O(L)。空间取决于所有字符串去重后的前缀节点总数,而不是字符串数量本身。
字符集固定且很小时,可用数组代替映射以降低哈希开销;字符集较大或分支稀疏时,映射更节省空间。大规模词典还要关注节点对象数量、映射对象开销和内存碎片。
删除操作不能直接移除整条路径。应从单词末尾向根回溯,仅删除既不是其他单词终点、也没有子节点的节点,否则会破坏共享前缀。