介绍
Trie 也叫字典树、前缀树。Trie 只处理字符串。
当我们通过搜索的方式查找字符串时，假设有 n 个条目，当使用线性结构时，查找复杂度为 O(n)；当使用树结构时，查找复杂度为 O(logn)，这个复杂度虽然已经很好了，但是它依然和数据量呈正相关，当数据量非常大时，查找速度依然会变慢。但是当使用 Trie 完成时，它可以做到查找速度和数据量无关，只和要查找的字符串长度有关。
Trie 是一棵多叉树，比如要存储的字符串只包含 26 个小写字母，那么每个节点就最多包含 26 个叉。
1
2
3
4
5
6
7
| root
/ / \
a(*) c h
| | |
t(*) a i(*)
/ \
r(*) t(*)
|
上面这个 Trie 一共存了 a、at、car、cat、hi 这几个单词，因为有些单词是其他单词的一部分，所以需要一个额外的布尔 isWord 来标记这个节点是否是一个单词。可以看到，查询的时候，不管这棵树中存多少个单词，查询的深度都是单词的长度，这就是 Trie 的优势。同时，Trie 查询是否有单词以某个字符串为前缀会特别方便，因此 Trie 也叫前缀树。
Trie 的查询操作和其中包含多少个字符串是无关的，只和要查询的字符串长度有关。因此，如果有非常多的字符串，我们使用 Trie 进行查询效率是非常高的。
这里实现的 Trie 不具有删除操作，应用中也是可以添加删除操作的。
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
66
67
68
69
70
71
72
73
74
| public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
public int getSize() {
return size;
}
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;
}
}
|