字典树又称前缀树,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