本文概览：本文以LeetCode题目"实现 Trie (前缀树)"为例，讲解前缀树的结构设计——节点含 isWord 字段和 HashMap 邻接表，以及 insert/search/startsWith 三个核心操作

一、题目

![[实现Trie前缀树题目.png]]

二、题目分析

题目要求实现三个操作：

  • insert(word)：插入一个单词
  • search(word)：判断单词是否在树中（精确匹配）
  • startsWith(prefix)：判断树中是否有以 prefix 为前缀的单词

Trie 本质上是一个有向无环图，每个节点往下延伸，不会回头。所以和上一篇课程表一样，要用邻接表来存储节点之间的连接关系

但有个关键问题：如果存了 "apple"，搜索 "app" 应该返回 false——因为只存了 "apple" 这个单词，没存 "app"。怎么区分"经过这个节点"和"在这个节点结束了一个单词"？需要给每个节点加一个 isWord 字段，标记这个节点是否是某个单词的结尾

思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Trie {
    private final TrieNode root;

    public static class TrieNode {
        boolean isWord;
        Map<Character, TrieNode> children;

        TrieNode() {
            children = new HashMap<>();
            isWord = false;
        }
    }

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for(char c: word.toCharArray()) {
            // 如果当前节点的子节点中不存在字符c，就创建一个子节点,并更新当前节点为新创建的子节点
            cur = cur.children.computeIfAbsent(c, k -> new TrieNode());
        }
        cur.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode cur = root;
        for(char c: word.toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) {
                return false;
            }
        }
        return cur.isWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for(char c: prefix.toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) {
                return false;
            }
        }
        return true;
    }
}

思路简要说明

  1. 节点设计：TrieNode 包含两个字段——isWord（是否单词结尾）和 children（HashMap 邻接表，key 是字符，value 是子节点）
  2. insert：从 root 开始，逐个字符往下走，不存在就创建，走完后把最后一个节点的 isWord 设为 true
  3. search：逐个字符往下找，找不到返回 false，走完后还要检查 isWord 是否为 true
  4. startsWith：和 search 一样往下找，但走完后不需要检查 isWord，直接返回 true

三、思路详解

第一步：为什么需要 isWord 字段？

Trie 的每个节点代表路径上的一个字符位置。但"经过这个节点"和"在这个节点结束一个单词"是两回事

举例：存了 "apple"，路径是 a→p→p→l→e。此时搜索 "app"：

1
2
3
4
5
6
7
8
存了 "apple" 后的路径：

root
 └─ a
     └─ p
         └─ p
             └─ l
                 └─ e (isWord = true)

"app" 的路径 a→p→p 是存在的，但节点 p（第二个 p）不是任何单词的结尾，所以 search("app") 应该返回 false

如果不加 isWord 字段，只能判断路径是否存在，无法区分 "apple" 和 "app" 这种前缀相同但长度不同的情况。所以必须给节点加一个 isWord 字段，只有在 insert 一个单词的最后一个字符时才设为 true

第二步：邻接表的表示选择

每个节点需要存储"它下面有哪些子节点"。有三种选择：

方式 查找效率 空间开销 特点
List<TrieNode> O(n) 紧凑 需要遍历查找，效率低
TrieNode[26] O(1) 固定 26 个槽位 只能存 a-z，不够通用
Map<Character, TrieNode> O(1) 按需分配 通用、代码简单，效率略低但区别不大

本文采用 HashMap，因为代码最简单、最通用，效率差异可以忽略

第三步：insert 的完整过程

以插入 "apple" 为例，逐字符演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
初始状态：root 的 children = {}

字符 'a'：
  root.children 没有 'a'，创建新节点 node_a
  cur 移动到 node_a
  
字符 'p'：
  node_a.children 没有 'p'，创建新节点 node_p1
  cur 移动到 node_p1
  
字符 'p'：
  node_p1.children 没有 'p'，创建新节点 node_p2
  cur 移动到 node_p2
  
字符 'l'：
  node_p2.children 没有 'l'，创建新节点 node_l
  cur 移动到 node_l
  
字符 'e'：
  node_l.children 没有 'e'，创建新节点 node_e
  cur 移动到 node_e

循环结束，设置 cur.isWord = true

构建完后的结构：

1
2
3
4
5
6
root
 └─ a
     └─ p
         └─ p
             └─ l
                 └─ e (isWord = true)

第四步：前缀共享——insert "app" 再 insert "apple"

前缀树的核心优势就是公共前缀共享节点。先插入 "app"，再插入 "apple"：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
插入 "app" 后：

root
 └─ a
     └─ p
         └─ p (isWord = true)

插入 "apple" 时：
  字符 'a'：root.children 有 'a'，复用 → cur = node_a
  字符 'p'：node_a.children 有 'p'，复用 → cur = node_p1
  字符 'p'：node_p1.children 有 'p'，复用 → cur = node_p2
  字符 'l'：node_p2.children 没有 'l'，创建 → cur = node_l
  字符 'e'：node_l.children 没有 'e'，创建 → cur = node_e
  设置 node_e.isWord = true

最终结构：
root
 └─ a
     └─ p
         └─ p (isWord = true)    ← "app" 的结尾
             └─ l
                 └─ e (isWord = true)  ← "apple" 的结尾

"app" 和 "apple" 共享了 a→p→p 这三个节点，"apple" 只是在 "app" 的基础上往下延伸了两个节点。这就是前缀树节省空间的原理

第五步：search 和 startsWith 的区别

两者都是逐字符往下找，区别只在最后一步：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
search("app")：
  a → p → p 都存在
  检查 node_p2.isWord → true → 返回 true

search("ap")：
  a → p 都存在
  检查 node_p1.isWord → false → 返回 false

startsWith("ap")：
  a → p 都存在
  不检查 isWord → 直接返回 true

startsWith("apple")：
  a → p → p → l → e 都存在
  不检查 isWord → 直接返回 true

search 关心的是"这个单词存过没有"，所以必须检查 isWord；startsWith 关心的是"有没有单词以这个前缀开头"，只要路径存在就行，不需要检查 isWord

第六步：代码核心——computeIfAbsent

insert 里用了一个简洁的写法：

1
cur = cur.children.computeIfAbsent(c, k -> new TrieNode());

computeIfAbsent 的作用：如果 map 中有 key=c，返回对应的 value；如果没有，执行 lambda 创建新节点并放入 map，然后返回。一行代码完成了"没有就创建，然后移动到子节点"三步操作

复杂度分析

  • insert：O(m)，m 是单词长度，每个字符处理一次
  • search：O(m)，m 是单词长度
  • startsWith：O(m)，m 是前缀长度
  • 空间复杂度：O(N×m)，N 是单词数，m 是平均长度。有公共前缀的单词共享节点