Trie树（前缀树）的实现与应用_实现 trie (前缀树)

作者：神奇cpp | 2024-08-17 23:07:45

踩

实现 trie (前缀树)

Trie树，也被称为前缀树，是一种用于处理字符串的数据结构。它可以高效地进行字符串的插入、删除和搜索操作，并且能够快速找到具有相同前缀的字符串。本篇博客将详细介绍Trie树的实现原理和应用场景，并给出Java代码示例。

Trie树的基本结构

Trie树的基本结构由节点和边组成，每个节点表示一个字符，每条边表示一个字符的连接。从根节点到叶子节点的路径表示一个完整的字符串。
在Java代码示例中，我们定义了两种Trie树的实现方式。 Trie1 使用数组作为节点的存储结构， Trie2 使用哈希表作为节点的存储结构。两种实现方式在时间复杂度上没有本质的差异，只是在空间复杂度上有所不同。

Trie树的基本操作

Trie树的基本操作包括插入、删除、搜索和前缀匹配。

插入操作

插入操作用于将一个字符串插入到Trie树中。具体步骤如下：

从根节点开始，遍历字符串的每个字符。
对于每个字符，判断是否存在与之对应的子节点。
- 如果不存在，则创建一个新的节点，并将其作为当前节点的子节点。
- 如果存在，则将当前节点指向该子节点。
在遍历完所有字符后，将当前节点的 end 计数加一，表示该字符串的插入次数。

删除操作

删除操作用于从Trie树中删除一个字符串。具体步骤如下：

首先通过搜索操作判断该字符串是否存在于Trie树中。
如果存在，则从根节点开始，遍历字符串的每个字符。
对于每个字符，判断是否存在与之对应的子节点。
- 如果存在，则将当前节点指向该子节点。
- 如果不存在，则返回，表示该字符串不存在于Trie树中。
在遍历完所有字符后，将当前节点的 end 计数减一。
如果当前节点的 pass 计数为0，表示该节点没有其他字符串经过，可以将其删除。

搜索操作

搜索操作用于判断一个字符串在Trie树中出现的次数。具体步骤如下：

从根节点开始，遍历字符串的每个字符。
对于每个字符，判断是否存在与之对应的子节点。
- 如果存在，则将当前节点指向该子节点。
- 如果不存在，则返回0，表示该字符串不存在于Trie树中。
在遍历完所有字符后，返回当前节点的 end 计数，即表示该字符串在Trie树中出现的次数。

前缀匹配操作

前缀匹配操作用于统计所有以给定前缀开头的字符串的出现次数。具体步骤如下：

从根节点开始，遍历前缀字符串的每个字符。
对于每个字符，判断是否存在与之对应的子节点。
- 如果存在，则将当前节点指向该子节点。
- 如果不存在，则返回0，表示没有以该前缀开头的字符串。
在遍历完所有字符后，返回当前节点的 pass 计数，即表示所有以该前缀开头的字符串的出现次数。

示例与测试

在代码示例中，我们通过随机生成字符串数组的方式进行了多次测试，分别使用 Trie1 、 Trie2 和 Right （正确的实现方式）进行插入、删除、搜索和前缀匹配操作，并对结果进行了比较验证。
// 示例代码


import java.util.HashMap;

// 该程序完全正确
public class TrieTree {

    public static class Node1 {
        public int pass;//记录字符经过的个数
        public int end;//记录字符结束的个数
        public Node1[] nexts;//节点数组

        // char tmp = 'b'  (tmp - 'a')
        public Node1() {
            pass = 0;
            end = 0;
            nexts = new Node1[26];
        }
    }

    public static class Trie1 {
        private Node1 root;

        public Trie1() {
            root = new Node1();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] str = word.toCharArray();
            Node1 node = root;//头节点
            node.pass++;//有字符经过时
            int path = 0;
            for (int i = 0; i < str.length; i++) { // 从左往右遍历字符
                path = str[i] - 'a'; // 由字符，对应成走向哪条路
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node1();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node1 node = root;
                node.pass--;
                int path = 0;
                for (int i = 0; i < chs.length; i++) {
                    path = chs[i] - 'a';
                    if (--node.nexts[path].pass == 0) {
                        node.nexts[path] = null;
                        return;
                    }
                    node = node.nexts[path];
                }
                node.end--;
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

    public static class Node2 {
        public int pass;
        public int end;
        public HashMap<Integer, Node2> nexts;

        public Node2() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    public static class Trie2 {
        private Node2 root;

        public Trie2() {
            root = new Node2();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            node.pass++;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    node.nexts.put(index, new Node2());
                }
                node = node.nexts.get(index);
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word) {
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = (int) chs[i];
                    if (--node.nexts.get(index).pass == 0) {
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }
        }

        // word这个单词之前加入过几次
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end;
        }

        // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass;
        }
    }

    public static class Right {

        private HashMap<String, Integer> box;

        public Right() {
            box = new HashMap<>();
        }

        public void insert(String word) {
            if (!box.containsKey(word)) {
                box.put(word, 1);
            } else {
                box.put(word, box.get(word) + 1);
            }
        }

        public void delete(String word) {
            if (box.containsKey(word)) {
                if (box.get(word) == 1) {
                    box.remove(word);
                } else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        public int search(String word) {
            if (!box.containsKey(word)) {
                return 0;
            } else {
                return box.get(word);
            }
        }

        public int prefixNumber(String pre) {
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }
    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            Trie1 trie1 = new Trie1();
            Trie2 trie2 = new Trie2();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    trie2.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    trie2.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.search(arr[j]);
                    int ans2 = trie2.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                } else {
                    int ans1 = trie1.prefixNumber(arr[j]);
                    int ans2 = trie2.prefixNumber(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");

    }

}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297

总结

Trie树是一种高效的字符串处理数据结构，适用于各种需要快速搜索、插入和删除字符串的场景。本篇博客介绍了Trie树的原理和实现方式，并给出了Java代码示例。希望本篇博客能够帮助读者更好地理解和应用Trie树。
以上就是对Trie树的详细介绍和应用场景的博客。希望对您有所帮助。如有任何疑问，请随时提问。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/994776