本文介绍前缀树这一数据结构。首先从基本定义出发，阐述其核心特性，给出图解示例。随后通过基于数组的标准实现代码，讨论常见优化方法和变种结构。最后，与KMP字符串匹配算法进行对比分析，客观指出其优势与局限。
基本概念
定义
前缀树（Trie树），又称字典树，是一种树形数据结构，专门用于高效存储和检索字符串。
核心特性
它的核心特性是利用字符串的公共前缀来减少查询时间，特别适合处理前缀匹配、自动补全、拼写检查等场景。
图解示例
以字符串集合 [“apple”, “app”, “banana”] 为例。
1
2
3
4
5
6
7
8
9
10
11
12
13
| ●
/ \
a b
/ \
p a
/ \ \
p* p n
| \ \
l e* a
\ \
e* n
\
a*
|
代码实现
接下来，我们通过java代码实现基于数组的Trie树。树节点结构如下：
1
2
3
4
5
6
7
8
9
10
| private class TrieNode {
private TrieNode[] children;
private boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
|
插入操作
1
2
3
4
5
6
7
8
9
10
11
12
| public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}
|
查询操作
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
|
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
int index = c - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
|
删除操作
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
|
public void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode node, String word, int index) {
if (index == word.length()) {
if (!node.isEnd) {
return false;
}
node.isEnd = false;
return isEmptyNode(node);
}
char c = word.charAt(index);
int pos = c - 'a';
if (node.children[pos] == null) {
return false;
}
boolean shouldDeleteChild = delete(node.children[pos], word, index + 1);
if (shouldDeleteChild) {
node.children[pos] = null;
return !node.isEnd && isEmptyNode(node);
}
return false;
}
private boolean isEmptyNode(TrieNode node) {
for (TrieNode child : node.children) {
if (child != null) {
return false;
}
}
return true;
}
|
优化与变种
压缩 Trie（Radix Tree）
标准Trie下，每多一个字符就会多一个数组，存储消耗更大。我们可以对其进行压缩优化，即把连续节点合并为一个节点，存储整个字符串片段（而不是单个字符）。这种做法可以显著减少节点数量，降低树的高度，提高查询速度。相关伪代码如下：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| public class CompressedTrie {
private TrieNode root = new TrieNode();
private static class TrieNode {
String fragment = "";
Map<Character, TrieNode> children = new HashMap<>();
boolean isEnd = false;
public TrieNode() {
}
public TrieNode(String fragment) {
this.fragment = fragment;
}
}
public void insert(String word) {
insert(root, word);
}
private void insert(TrieNode node, String word) {
char firstChar = word.charAt(0);
TrieNode child = node.children.get(firstChar);
if (child == null) {
TrieNode newNode = new TrieNode(word);
newNode.isEnd = true;
node.children.put(firstChar, newNode);
} else {
String fragment = child.fragment;
int commonPrefixLen = getCommonPrefixLength(fragment, word);
if (commonPrefixLen == fragment.length()) {
insert(child, word.substring(commonPrefixLen));
} else {
String commonPrefix = fragment.substring(0, commonPrefixLen);
String remainingFragment = fragment.substring(commonPrefixLen);
String remainingWord = word.substring(commonPrefixLen);
TrieNode splitNode = new TrieNode(commonPrefix);
node.children.put(firstChar, splitNode);
child.fragment = remainingFragment;
splitNode.children.put(remainingFragment.charAt(0), child);
if (!remainingWord.isEmpty()) {
TrieNode newNode = new TrieNode(remainingWord);
newNode.isEnd = true;
splitNode.children.put(remainingWord.charAt(0), newNode);
} else {
splitNode.isEnd = true;
}
}
}
}
}
|
三向 Trie（TST）
三向Trie也是是标准 Trie 的一种变体。标准 Trie 使用固定大小的数组存储子节点，而 TST 改用左、中、右三个指针。在稀疏数据的场景下，这种做法可以更高效的存储。
1
2
3
4
5
6
7
8
9
10
| private class TSTNode {
TSTNode left, mid, right;
char c;
boolean isEnd;
}
|
Trie vs KMP
| 操作 |
Trie |
KMP |
| 预处理 |
O(m * n) （n 为字符串数量，m 为平均长度） |
O(m) （仅需计算模式串的LPS数组） |
| 单次查询 |
O(m) （m 为查询字符串长度） |
O(n) （n 为主串长度，匹配阶段） |
| 多模式查询 |
O(k * m)（k 为查询次数） |
O(k * (n + m)) （k 为查询次数） |
总结：
