1.1、什么是Trie树

    Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。
  

1.2、树的构建举个在网上流传颇广的例子，如下：
    题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
    分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。
    现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。
    好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们构建的树就是如下图这样的：

  当时第一次看到这幅图的时候，便立马感到此树之不凡构造了。单单从上幅图便可窥知一二，好比大海搜人，立马就能确定东南西北中的到底哪个方位，如此迅速缩小查找的范围和提高查找的针对性，不失为一创举。
    ok，如上图所示，对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
    那么，对于一个单词，我只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
    这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。
    我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。

1.3、Trie树java实例

1. 
   
2. <P> </P>
   
3. <DIV class=blockcode>
   
4. <BLOCKQUOTE>import java.util.ArrayList;
   
5. import java.util.Iterator;
   
6. import java.util.List;
   
7. 
   
8. 
   
9. /**
   
10. * A word trie which can only deal with 26 alphabeta letters.
    
11. */
    
12. 
    
13. public class Trie{
    
14. 
    
15. private Vertex root;//一个Trie树有一个根节点
    
16. 
    
17. //内部类
    
18. protected class Vertex{//节点类
    
19. protected int words;
    
20. protected int prefixes;
    
21. protected Vertex[] edges;//每个节点包含26个子节点(类型为自身)
    
22. Vertex() {
    
23. words = 0;
    
24. prefixes = 0;
    
25. edges = new Vertex[26];
    
26. for (int i = 0; i < edges.length; i++) {
    
27. edges[i] = null;
    
28. }
    
29. }
    
30. }
    
31. 
    
32. public Trie () {
    
33. root = new Vertex();
    
34. }
    
35. 
    
36. 
    
37. /** *//**
    
38. * List all words in the Trie.
    
39. * @return
    
40. */
    
41. 
    
42. public List< String> listAllWords() {
    
43. 
    
44. List< String> words = new ArrayList< String>();
    
45. Vertex[] edges = root.edges;
    
46. 
    
47. for (int i = 0; i < edges.length; i++) {
    
48. if (edges[i] != null) {
    
49. String word = "" + (char)('a' + i);
    
50. depthFirstSearchWords(words, edges[i], word);
    
51. }
    
52. }
    
53. return words;
    
54. }
    
55. 
    
56. /** *//**
    
57. * Depth First Search words in the Trie and add them to the List.
    
58. *
    
59. * @param words
    
60. * @param vertex
    
61. * @param wordSegment
    
62. */
    
63. 
    
64. private void depthFirstSearchWords(List words, Vertex vertex, String wordSegment) {
    
65. Vertex[] edges = vertex.edges;
    
66. boolean hasChildren = false;
    
67. for (int i = 0; i < edges.length; i++) {
    
68. if (edges[i] != null) {
    
69. hasChildren = true;
    
70. String newWord = wordSegment + (char)('a' + i);
    
71. depthFirstSearchWords(words, edges[i], newWord);
    
72. }
    
73. }
    
74. if (!hasChildren) {
    
75. words.add(wordSegment);
    
76. }
    
77. }
    
78. 
    
79. public int countPrefixes(String prefix) {
    
80. return countPrefixes(root, prefix);
    
81. }
    
82. 
    
83. private int countPrefixes(Vertex vertex, String prefixSegment) {
    
84. if (prefixSegment.length() == 0) { //reach the last character of the word
    
85. return vertex.prefixes;
    
86. }
    
87. 
    
88. char c = prefixSegment.charAt(0);
    
89. int index = c - 'a';
    
90. if (vertex.edges[index] == null) { // the word does NOT exist
    
91. return 0;
    
92. } else {
    
93. 
    
94. return countPrefixes(vertex.edges[index], prefixSegment.substring(1));
    
95. 
    
96. }
    
97. 
    
98. }
    
99. 
    
100. public int countWords(String word) {
     
101. return countWords(root, word);
     
102. }
     
103. 
     
104. private int countWords(Vertex vertex, String wordSegment) {
     
105. if (wordSegment.length() == 0) { //reach the last character of the word
     
106. return vertex.words;
     
107. }
     
108. 
     
109. char c = wordSegment.charAt(0);
     
110. int index = c - 'a';
     
111. if (vertex.edges[index] == null) { // the word does NOT exist
     
112. return 0;
     
113. } else {
     
114. return countWords(vertex.edges[index], wordSegment.substring(1));
     
115. 
     
116. }
     
117. 
     
118. }
     
119. 
     
120. 
     
121. /** *//**
     
122. * Add a word to the Trie.
     
123. * @param word The word to be added.
     
124. */
     
125. 
     
126. public void addWord(String word) {
     
127. addWord(root, word);
     
128. }
     
129. 
     
130. 
     
131. /** *//**
     
132. * Add the word from the specified vertex.
     
133. * @param vertex The specified vertex.
     
134. * @param word The word to be added.
     
135. */
     
136. 
     
137. private void addWord(Vertex vertex, String word) {
     
138. if (word.length() == 0) { //if all characters of the word has been added
     
139. vertex.words ++;
     
140. } else {
     
141. vertex.prefixes ++;
     
142. char c = word.charAt(0);
     
143. c = Character.toLowerCase(c);
     
144. int index = c - 'a';
     
145. if (vertex.edges[index] == null) { //if the edge does NOT exist
     
146. vertex.edges[index] = new Vertex();
     
147. }
     
148. 
     
149. addWord(vertex.edges[index], word.substring(1)); //go the the next character
     
150. }
     
151. }
     
152. 
     
153. public static void main(String args[]) //Just used for test
     
154. {
     
155. Trie trie = new Trie();
     
156. trie.addWord("China");
     
157. trie.addWord("China");
     
158. trie.addWord("China");
     
159. 
     
160. trie.addWord("crawl");
     
161. trie.addWord("crime");
     
162. trie.addWord("ban");
     
163. trie.addWord("China");
     
164. 
     
165. trie.addWord("english");
     
166. trie.addWord("establish");
     
167. trie.addWord("eat");
     
168. System.out.println(trie.root.prefixes);
     
169. System.out.println(trie.root.words);
     
170. 
     
171. 
     
172. 
     
173. List< String> list = trie.listAllWords();
     
174. Iterator listiterator = list.listIterator();
     
175. 
     
176. while(listiterator.hasNext())
     
177. {
     
178. String s = (String)listiterator.next();
     
179. System.out.println(s);
     
180. }
     
181. 
     
182. 
     
183. int count = trie.countPrefixes("ch");
     
184. int count1=trie.countWords("china");
     
185. System.out.println("the count of c prefixes:"+count);
     
186. System.out.println("the count of china countWords:"+count1);
     
187. 
     
188. 
     
189. }
     
190. }
     

复制代码

挺抽象的。。

周景新 发表于 2015-1-10 14:40
挺抽象的。。

其实还好啦，理解下他的结构和作用可以了。