数据结构与算法 / 系统课时

字典树

字典树

字典树用于高效保存和查询大量字符串,核心做法是让具有相同前缀的单词共享路径。本课将用一个支持中英文的 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,它能正确处理基本多文种平面之外的字符;若业务要求按用户可见字素处理,还需要额外的文本分段规则。

完整可运行示例

java
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 或更高版本的环境中执行:

bash
javac TrieDemo.java
java TrieDemo

预期输出:

text
查找 java: true
查找 jav: false
前缀 jav: true
查找 算法: true
前缀 算: true
查找 数据: false

jav 的路径已经存在,但最终节点没有结束标记,因此完整查询为 false,前缀查询为 true。

复杂度与工程取舍

设输入字符串含 L 个代码点。在哈希映射平均常数时间访问的前提下,插入、完整查询和前缀查询均为 O(L)。空间取决于所有字符串去重后的前缀节点总数,而不是字符串数量本身。

字符集固定且很小时,可用数组代替映射以降低哈希开销;字符集较大或分支稀疏时,映射更节省空间。大规模词典还要关注节点对象数量、映射对象开销和内存碎片。

删除操作不能直接移除整条路径。应从单词末尾向根回溯,仅删除既不是其他单词终点、也没有子节点的节点,否则会破坏共享前缀。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

字典树

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通