学步园

http://www.java3z.com/cwbwebhome/article/article19/res056.html?id=3867

来源于英文“retrieval”.   Trie树就是字符树，其核心思想就是空间换时间。

举个简单的例子。
   给你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个单词，我们构建的树就是这样的。

        对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
   那么，对于一个单词，我只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。

在http://www.java3z.com/cwbwebhome/article/article19/res056.html?id=3867给出了一个实现代码

import java.util.ArrayList;<br /> import java.util.Iterator;<br /> import java.util.List;</p> <p>/** *//**<br /> * A word trie which can only deal with 26 alphabeta letters.<br /> * @author Leeclipse<br /> * @since 2007-11-21<br /> */</p> <p>public class Trie1{</p> <p> private Vertex root;//一个Trie树有一个根节点</p> <p> //内部类<br /> protected class Vertex{//节点类<br /> protected int words;<br /> protected int prefixes;<br /> protected Vertex[] edges;//每个节点包含26个子节点(类型为自身)<br /> Vertex() {<br /> words = 0;<br /> prefixes = 0;<br /> edges = new Vertex[26];<br /> for (int i = 0; i < edges.length; i++) {<br /> edges[i] = null;<br /> }<br /> }<br /> }</p> <p> public Trie1 () {<br /> root = new Vertex();<br /> }</p> <p> /** *//**<br /> * List all words in the Trie.<br /> *<br /> * @return<br /> */</p> <p> public List< String> listAllWords() {</p> <p> List< String> words = new ArrayList< String>();<br /> Vertex[] edges = root.edges;</p> <p> for (int i = 0; i < edges.length; i++) {<br /> if (edges[i] != null) {<br /> String word = "" + (char)('a' + i);<br /> depthFirstSearchWords(words, edges[i], word);<br /> }<br /> }<br /> return words;<br /> }</p> <p> /** *//**<br /> * Depth First Search words in the Trie and add them to the List.<br /> *<br /> * @param words<br /> * @param vertex<br /> * @param wordSegment<br /> */</p> <p> private void depthFirstSearchWords(List<String> words, Vertex vertex, String wordSegment) {<br /> Vertex[] edges = vertex.edges;<br /> boolean hasChildren = false;<br /> for (int i = 0; i < edges.length; i++) {<br /> if (edges[i] != null) {<br /> hasChildren = true;<br /> String newWord = wordSegment + (char)('a' + i);<br /> depthFirstSearchWords(words, edges[i], newWord);<br /> }<br /> }<br /> if (!hasChildren) {<br /> words.add(wordSegment);<br /> }<br /> }</p> <p> public int countPrefixes(String prefix) {<br /> return countPrefixes(root, prefix);<br /> }</p> <p> private int countPrefixes(Vertex vertex, String prefixSegment) {<br /> if (prefixSegment.length() == 0) { //reach the last character of the word<br /> return vertex.prefixes;<br /> }</p> <p> char c = prefixSegment.charAt(0);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { // the word does NOT exist<br /> return 0;<br /> } else {</p> <p> return countPrefixes(vertex.edges[index], prefixSegment.substring(1));</p> <p> } </p> <p> }</p> <p> public int countWords(String word) {<br /> return countWords(root, word);<br /> } </p> <p> private int countWords(Vertex vertex, String wordSegment) {<br /> if (wordSegment.length() == 0) { //reach the last character of the word<br /> return vertex.words;<br /> }</p> <p> char c = wordSegment.charAt(0);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { // the word does NOT exist<br /> return 0;<br /> } else {<br /> return countWords(vertex.edges[index], wordSegment.substring(1));</p> <p> } </p> <p> }</p> <p> /** *//**<br /> * Add a word to the Trie.<br /> *<br /> * @param word The word to be added.<br /> */</p> <p> public void addWord(String word) {<br /> addWord(root, word);<br /> }</p> <p> /** *//**<br /> * Add the word from the specified vertex.<br /> * @param vertex The specified vertex.<br /> * @param word The word to be added.<br /> */</p> <p> private void addWord(Vertex vertex, String word) {<br /> if (word.length() == 0) { //if all characters of the word has been added<br /> vertex.words ++;<br /> } else {<br /> vertex.prefixes ++;<br /> char c = word.charAt(0);<br /> c = Character.toLowerCase(c);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { //if the edge does NOT exist<br /> vertex.edges[index] = new Vertex();<br /> }</p> <p> addWord(vertex.edges[index], word.substring(1)); //go the the next character<br /> }<br /> }</p> <p> public static void main(String args[]) //Just used for test<br /> {<br /> Trie1 trie = new Trie1();<br /> trie.addWord("China");<br /> trie.addWord("China");<br /> trie.addWord("China");</p> <p> trie.addWord("crawl");<br /> trie.addWord("crime");<br /> trie.addWord("ban");<br /> trie.addWord("China");</p> <p> trie.addWord("english");<br /> trie.addWord("establish");<br /> trie.addWord("eat");<br /> trie.addWord("a");<br /> trie.addWord("ab");<br /> System.out.println(trie.root.prefixes);<br /> System.out.println(trie.root.words);<br /> List< String> list = trie.listAllWords();<br /> Iterator<String> listiterator = list.listIterator();<br /> while(listiterator.hasNext())<br /> {<br /> String s = (String)listiterator.next();<br /> System.out.println(s);<br /> }<br /> int count = trie.countPrefixes("a");<br /> int count1=trie.countWords("china");<br /> System.out.println("the count of a prefixes:"+count);<br /> System.out.println("the count of china countWords:"+count1);<br /> }<br /> }<br />

该代码是不完全的，因为值输出了叶子节点。如果出现形如“abc”,"ab"这样的结果，就不能输出"ab"

我的修正思路：

在vertex类里面增加一个boolean量：isEntire;在后面的操作中，只要isEntire为true，那么，就输出。

修正后的代码及其测试代码如下：

import java.util.ArrayList;<br /> import java.util.List;<br /> public class Trie{<br /> private Vertex root;//一个Trie树有一个根节点<br /> //内部类<br /> protected class Vertex{ //节点类<br /> protected int words;<br /> protected int prefixes; //前缀个数 -- add by randy 2011.5.24<br /> protected boolean isEntire;<br /> protected Vertex[] edges;//每个节点包含26个子节点(类型为自身)<br /> Vertex() {<br /> words = 0;<br /> prefixes = 0;<br /> edges = new Vertex[26];<br /> for (int i = 0; i < edges.length; i++) {<br /> edges[i] = null;<br /> }<br /> }<br /> }<br /> public Trie () {<br /> root = new Vertex();<br /> }<br /> /** *//**<br /> * Add a word to the Trie.<br /> *<br /> * @param word The word to be added.<br /> */</p> <p> public void addWord(String word) {<br /> addWord(root, word);<br /> }</p> <p> /** *//**<br /> * Add the word from the specified vertex.<br /> * @param vertex The specified vertex.<br /> * @param word The word to be added.<br /> * 调用的时候都是addWord(root,word) -- add by randy 2011.5.24<br /> */</p> <p>private void addWord(Vertex vertex, String word) {<br /> if (word.length() == 0)<br /> {<br /> // vertex.words ++;<br /> vertex.prefixes ++;<br /> vertex.isEntire = true;<br /> return;<br /> }<br /> vertex.prefixes ++;<br /> char c = word.charAt(0);<br /> c = Character.toLowerCase(c);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { //if the edge does NOT exist<br /> vertex.edges[index] = new Vertex();<br /> }<br /> addWord(vertex.edges[index], word.substring(1)); //go the the next character<br /> }<br /> // }<br /> /** *//**<br /> * List all words in the Trie.<br /> *<br /> * @return<br /> */<br /> public List<String> listAllWords() {<br /> List<String> words = new ArrayList< String>();<br /> Vertex[] edges = root.edges;<br /> for (int i = 0; i < edges.length; i++) {<br /> if (edges[i] != null) {<br /> String word = "" + (char)('a' + i);<br /> if(edges[i].isEntire)<br /> words.add(word);<br /> depthFirstSearchWords(words, edges[i], word);<br /> }<br /> }<br /> return words;<br /> }</p> <p> /** *//**<br /> * Depth First Search words in the Trie and add them to the List.<br /> *<br /> * @param words<br /> * @param vertex<br /> * @param wordSegment<br /> */<br /> private boolean isHaveObject(Vertex[] edges)<br /> {<br /> for (int i = 0; i < edges.length; i++)<br /> if (edges[i] != null)<br /> return true;<br /> return false;<br /> }<br /> private void depthFirstSearchWords(List<String> words, Vertex vertex, String wordSegment) {<br /> Vertex[] edges = vertex.edges;<br /> for (int i = 0; i < edges.length; i++) {<br /> if (edges[i] != null) {<br /> String newWord = wordSegment + (char)('a' + i);<br /> if(edges[i].isEntire)<br /> words.add(newWord);<br /> depthFirstSearchWords(words, edges[i], newWord);<br /> }<br /> }<br /> }</p> <p> public int countPrefixes(String prefix) {<br /> return countPrefixes(root, prefix);<br /> }</p> <p> private int countPrefixes(Vertex vertex, String prefixSegment) {<br /> if (prefixSegment.length() == 0) { //reach the last character of the word<br /> return vertex.prefixes;<br /> }<br /> char c = prefixSegment.charAt(0);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { // the word does NOT exist<br /> return 0;<br /> } else {<br /> return countPrefixes(vertex.edges[index], prefixSegment.substring(1));<br /> }<br /> }<br /> public int countWords(String word) {<br /> return countWords(root, word);<br /> }<br /> private int countWords(Vertex vertex, String wordSegment) {<br /> if (wordSegment.length() == 0) { //reach the last character of the word<br /> return vertex.words;<br /> }<br /> char c = wordSegment.charAt(0);<br /> int index = c - 'a';<br /> if (vertex.edges[index] == null) { // the word does NOT exist<br /> return 0;<br /> } else {<br /> return countWords(vertex.edges[index], wordSegment.substring(1));<br /> }<br /> }<br /> public static void main(String args[]) //Just used for test<br /> {<br /> Trie trie = new Trie();<br /> trie.addWord("China");<br /> trie.addWord("Chi");<br /> trie.addWord("China");<br /> trie.addWord("crawl");<br /> trie.addWord("crime");<br /> trie.addWord("ban");<br /> trie.addWord("China");<br /> trie.addWord("english");<br /> trie.addWord("establish");<br /> trie.addWord("eat");<br /> // System.out.println(trie.root.prefixes);<br /> // System.out.println(trie.root.words);<br /> // List< String> list = trie.listAllWords();<br /> // Iterator<String> listiterator = list.listIterator();<br /> // while(listiterator.hasNext())<br /> // {<br /> // String s = (String)listiterator.next();<br /> // System.out.println(s);<br /> // }<br /> // int count = trie.countPrefixes("ch");<br /> // int count1=trie.countWords("china");<br /> // System.out.println("the count of c prefixes:"+count);<br /> // System.out.println("the count of china countWords:"+count1);</p> <p>// trie.addWord("b");<br /> // trie.addWord("b");<br /> // trie.addWord("bc");<br /> // trie.addWord("bcd");<br /> trie.addWord("ab");<br /> trie.addWord("abc");<br /> trie.addWord("a");<br /> System.out.println("the total count of trie tree is :" + trie.root.prefixes);<br /> // trie.addWord("china");<br /> // trie.addWord("chin");<br /> int count = trie.countPrefixes("ab");<br /> System.out.println("the count of ab prefixes:" + count);<br /> // trie.addWord("Chin");<br /> // trie.addWord("b");<br /> List< String> list = trie.listAllWords();<br /> for(String s : list)<br /> System.out.println(s);<br /> }<br /> }

输出结果：

the total count of trie tree is :13
the count of ab prefixes:2
a
ab
abc
ban
chi
china
crawl
crime
eat
english
establish