字典树
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
字典树又称前缀树，Trie树，顾名思义，它是一种型似字典的树形结构，主要用于快速检索字符串是否存在，查找时间复杂度时O(n)，n是查找的字符串长度。
比如说在集合['abc', 'abb', 'acc', 'aca', 'acb', 'acbd']中查找字符串'acbd'，一般来说我们会遍历集合，比较集合中的每一个字符串，如果集合较小，这种方式还行，如果集合特别大，这样效率就会非常低下，这种情况下就可以使用字典树来解决，下面看看字典树的结构。
如果要查找acbd，先从root出发，查找是否存在子节点a，存在，继续查找节点a是否存在子节点c，存在，继续查找节点c是否存在子节点b，存在，继续查找节点b是否存在子节点d，存在，查找完毕。很明显查找过程只和当前字符串长度有关，和集合中有多少元素并无关系。下面是字典树的简单实现。
trie一词来自 retrieval，即检索
注释1/**
2 * 字典树
3 */
4class TrieTree {
5
6 /**
7 * 字典树节点
8 */
9 static class Node {
10 /**
11 * 从根节点到当前节点是否是一个单词，有可能只是单词的一部分
12 */
13 boolean word;
14 /**
15 * 当前节点的字符
16 */
17 char ch;
18 /**
19 * 当前节点的子节点
20 */
21 Node[] childList = new Node[26];
22
23 Node() {
24 }
25
26 Node(char ch) {
27 this.ch = ch;
28 }
29 }
30
31 private final Node root;
32
33 public TrieTree() {
34 root = new Node();
35 }
36
37 /**
38 * 插入一个单词到字典树
39 *
40 * @param word 要插入的单词
41 */
42 public void insert(String word) {
43 Node parent = root;
44 for (int i = 0; i < word.length(); i++) {
45 char ch = word.charAt(i);
46 Node node = parent.childList[ch - 'a'];
47 if (node == null) {
48 node = new Node(ch);
49 }
50 parent.childList[ch - 'a'] = node;
51 parent = node;
52 }
53 parent.word = true;
54 }
55
56 /**
57 * 查找字符串是否存在
58 *
59 * @param word 要查询的字符串
60 * @return 是否存在
61 */
62 public boolean search(String word) {
63 Node parent = root;
64 for (int i = 0; i < word.length(); i++) {
65 char ch = word.charAt(i);
66 parent = parent.childList[ch - 'a'];
67 if (parent == null) {
68 return false;
69 }
70 }
71 return parent.word;
72 }
73}
74
75public class Main {
76
77 public static void main(String[] args) {
78 String[] set = {"abc", "abb", "acc", "aca", "acb", "acbd"};
79 TrieTree tree = new TrieTree();
80 for (String word : set) {
81 tree.insert(word);
82 }
83 System.out.println(tree.search("acbd"));
84 System.out.println(tree.search("ac"));
85 }
86}
87注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
字典树前缀树trie树
1