又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
下面是字典树数据的Java实现代码，字典树中存放的是26个英文字母
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| package coding_Interview_guide.ch5;
class trie {
// 根节点
private TrieNode root;
public trie() {
super();
this.root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0; // root的map[TrieNode]数组的下标
for (char ch : chs) {
index = ch - 'a';
if (node.map[index] == null) {
node.map[index] = new TrieNode();
}
node = node.map[index]; // 转到下一个字符的节点
node.path++; // 公用节点树加1
}
node.end++; // 结尾
}
public boolean search(String word) {
if (word == null) {
return false;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0; // root的map[TrieNode]数组的下标
for (char ch : chs) {
index = ch - 'a';
if (node.map[index] == null) {
return false;
} else {
node = node.map[index];
}
}
return node.end != 0;
}
public void delete(String word) {
if (search(word)) {
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0; // root的map[TrieNode]数组的下标
for (char ch : chs) {
index = ch - 'a';
if (node.map[index].path-- == 1) { // 最后一个节点的公用节点数减一,同时如果只有一个公用节点的话,直接置为null
node.map[index] = null;
return;
}
// 否则继续下一个节点
node = node.map[index]; // 转到下一个字符的节点
}
node.end--; // 结尾数减一
}
}
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0; // root的map[TrieNode]数组的下标
for (char ch : chs) {
index = ch - 'a';
if (node.map[index] == null) {
return 0;
}
node = node.map[index];
}
return node.path;
}
}
class TrieNode {
public int path; // 表示有多少个单词公用这个节点
public int end; // 表示有多少个单词以这个节点结尾
public TrieNode[] map;
public TrieNode() {
super();
this.path = 0;
this.end = 0;
this.map = new TrieNode[26];
}
}
public class Trie {
public static void main(String[] args) {
// TODO 自动生成的方法存根
trie t = new trie();
}
}
|
