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

Trie 树

Trie 树

Trie 树把字符串拆成逐字符路径,让拥有相同前缀的单词共享节点。它能够按查询串长度完成插入、完整单词查询和前缀查询。本课将实现一个仅接收小写英文字母的可运行 Trie,并明确单词结束标记的作用。

学习目标

  • 理解 Trie 节点、字符边和公共前缀共享机制。
  • 区分完整查询 search 与前缀查询 startsWith。
  • 能够实现插入、查询和输入边界校验。

结构与存储方式

Trie 的根节点不代表字符。从根开始,每条边对应一个字符;沿路径读取字符即可还原前缀或单词。多个单词共享相同前缀,因此 app、apple 和 apply 会共用 a → p → p 这段路径。

Trie 树公共前缀与结束标记

节点必须额外保存 wordEnd。仅仅能够走完路径,只能证明该字符串是某个已插入单词的前缀;只有末节点的 wordEnd 为 true,才能证明完整单词存在。

三个核心操作

插入

从根节点依次处理字符。对应子节点不存在时创建节点,存在时复用节点。处理完最后一个字符后,把当前节点标记为单词结束。

完整查询

沿字符路径查找目标单词。路径缺失时返回 false;路径存在但末节点未标记结束时也返回 false。例如插入 apple 后,search("app") 仍为 false,除非 app 也被单独插入。

前缀查询

前缀查询只要求路径存在,不检查末节点的 wordEnd。因此插入 apple 后,startsWith("app") 为 true。

完整可运行示例

下面使用长度为 26 的子节点数组保存 a 到 z。这种实现访问速度稳定,但输入范围固定。将代码保存为 TrieDemo.java。

java
public class TrieDemo {

    private static class TrieNode {
        private final TrieNode[] children = new TrieNode[26];
        private boolean wordEnd;
    }

    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode current = root;

        for (char ch : word.toCharArray()) {
            int index = toIndex(ch);
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }

        // 只有完整单词的最后一个节点才标记结束。
        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) {
        TrieNode current = root;

        for (char ch : text.toCharArray()) {
            int index = toIndex(ch);
            current = current.children[index];
            if (current == null) {
                return null;
            }
        }

        return current;
    }

    private static int toIndex(char ch) {
        if (ch < 'a' || ch > 'z') {
            throw new IllegalArgumentException("只支持小写英文字母: " + ch);
        }
        return ch - 'a';
    }

    public static void main(String[] args) {
        TrieDemo trie = new TrieDemo();
        trie.insert("apple");
        trie.insert("app");
        trie.insert("apply");
        trie.insert("bat");

        System.out.println("search(app): " + trie.search("app"));
        System.out.println("search(ap): " + trie.search("ap"));
        System.out.println("startsWith(ap): " + trie.startsWith("ap"));
        System.out.println("startsWith(cat): " + trie.startsWith("cat"));
    }
}

编译并运行:

bash
javac TrieDemo.java
java TrieDemo

预期输出

text
search(app): true
search(ap): false
startsWith(ap): true
startsWith(cat): false

复杂度与工程边界

设待处理字符串长度为 L,插入、完整查询和前缀查询的时间复杂度均为 O(L)。复杂度与 Trie 中已存单词总数没有直接线性关系,但节点数量可能接近所有字符数之和。

数组子节点适合字符集固定且较小的场景;若需要中文、符号或稀疏字符集,可把 TrieNode[] 改为 Map<Integer, TrieNode>,并按 Unicode 码点遍历。删除操作还需要判断节点是否被其他单词共享,不能直接切断整条路径。

常见错误

  • 不设置 wordEnd:会把所有前缀误判为完整单词。
  • search 与 startsWith 使用同一返回条件:完整查询必须额外检查结束标记。
  • 字符下标未校验:ch - 'a' 对大写字母或符号可能越界,示例通过 toIndex 明确拒绝非法字符。
  • 每次插入都覆盖已有子节点:这会破坏共享前缀,应只在子节点为空时创建新节点。

本课练习

  1. 插入 car、card、care 和 dog,验证 search("car")、search("ca") 与 startsWith("ca") 的结果。
  2. 增加 countPrefix(String prefix),返回具有指定前缀的单词数量;要求在节点中维护经过次数或子树单词数。
  3. 实现删除操作:删除一个存在的单词后保留仍被其他单词使用的公共节点,并给出删除前后的查询验收结果。

本课总结

  • Trie 通过共享字符前缀降低重复存储,并按字符串长度完成查询。
  • wordEnd 是区分完整单词与普通前缀的关键状态。
  • 子节点容器应根据字符集大小和稀疏程度选择数组或映射。

下一课预告

接下来可继续学习字符串多模式匹配、自动补全与词典检索,把 Trie 的前缀结构扩展为更完整的字符串处理工具。

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

目录与阅读设置

阅读设置

17

记录一个想法

Trie 树

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

登录哪都通