Trie的java实现
关注Trie 这种结构已经很久，Trie有一个很有趣的用途，那就是自动提示。而且，前不久在一次面试里，也需要用Trie来解答。所以，在此对这个数据结构进行总结。
Trie，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
它有3个基本性质：
有了这样一种数据结构，我们可以用它来保存一个字典，要查询改字典里是否有相应的词，是否非常的方便呢？我们也可以做智能提示，我们把用户已经搜索的词存在Trie里，每当用户输入一个词的时候，我们可以自动提示，比如当用户输入 ba, 我们会自动提示 bat 和 baii.
现在来讨论Trie的实现。
首先，我们定义一个Abstract Trie,Trie 里存放的是一个Node。这个类里有两个操作，一个是插入，另一个是查询。具体实现放在后面。
abstract class Trie() { private Node root; public Trie() { root = new Node(' '); } public void insert(String s); public boolean search(String s); }Node 类的实现
class Node { char content; boolean marker; LinkedList<Node> child; public Node(char c){ child = new LinkedList<Node>(); marker = false; content = c; } public Node subNode(char c){ if(child != null){ for(Node eachChild : child){ if(eachChild.content == c){ return eachChild; } } } return null; } }
现在我们来看这个Trie类的具体实现。
public class Trie{ private Node root; public Trie(){ root = new Node(' '); } public void insert(String s){ Node current = root; if(s.length() == 0) //For an empty character current.marker = true; for(int i = 0;i < s.length();i++){ Node child = current.subNode(s.charAt(i)); if(child != null){ current = child; } else { current.child.add(new Node(s.charAt(i))); current = current.subNode(s.charAt(i)); } // Set marker to indicate end of the word if(i==s.length()-1) current.marker = true; } } public boolean search(String s){ Node current = root; while(current != null){ for(int i=0;i<s.length();i++){ if(current.subNode(s.charAt(i)) == null) return false; else current = current.subNode(s.charAt(i)); } /* * This means that a string exists, but make sure its * a word by checking its 'marker' flag */ if (current.marker == true) return true; else return false; } return false; } }
时间复杂度分析：
对于insert, 如果被插入的String长度是 k, 每对一个字符进行查询，我们最多在child linkedlist里面查询26次（最多26个字母），所以，复杂度为O(26*k) = O(k). 对于 search, 复杂度是一样的。
本文代码来自：http://www.technicalypto.com/2010/04/trie-in-java.html
另一个版本的Trie的JAVA实现。思路是一样的，只是实现方式有少许区别。
import java.util.HashMap;
import java.util.Map;
public class Trie {
private static class Node {
private boolean isWord = false; // indicates a complete word
private int prefixes = 0; // indicates how many words have the prefix
private Map children = new HashMap(); // references to all possible children
}
private Node root = new Node();
/**
* Inserts a new word into the trie
* @param word
*/
public void insertWord(String word){
if(searchWord(word) == true) return;
Node current = root;
for(char c : word.toCharArray()){
if(current.children.containsKey(Character.valueOf(c))){
Node child = current.children.get(Character.valueOf(c));
child.prefixes++;
current = child;
}else{
Node child = new Node();
child.prefixes = 1;
current.children.put(Character.valueOf(c), child);
current = child;
}
}
// we have reached the endof the word, hence mark it true
// if during a search we reach the end of the search string and this
// flag is still false, then the search string is not registered as a valid
// word in the trie but is a prefix
current.isWord = true;
}
/**
* Searches for a word in the trie
* @param word
*/
public boolean searchWord(String word){
Node current = root;
for(char c : word.toCharArray()){
if(current.children.containsKey(Character.valueOf(c))){
current = current.children.get(Character.valueOf(c));
}else{
return false;
}
}
// if at the end of the search of entire word the boolean variable is
// still false means that the given word is not regitered as a valid
// word in the trie, but is a prefix
return current.isWord;
}
/**
* Deletes a word from the trie
* @param word
*/
public void deleteWord(String word){
if(searchWord(word) == false) return;
Node current = root;
for(char c : word.toCharArray()){
Node child = current.children.get(Character.valueOf(c));
if(child.prefixes == 1){
current.children.remove(Character.valueOf(c));
return;
}else{
child.prefixes--;
current = child;
}
}
// since the word is removed now, set the flag to false
current.isWord = false;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insertWord("ball");
trie.insertWord("balls");
trie.insertWord("bat");
trie.insertWord("doll");
trie.insertWord("dork");
trie.insertWord("dorm");
trie.insertWord("send");
trie.insertWord("sense");
// testing deletion
//System.out.println(trie.searchWord("ball"));
//trie.deleteWord("ball");
//System.out.println(trie.searchWord("ball"));
//System.out.println(trie.searchWord("balls"));
// testing insertion
//System.out.println(trie.searchWord("dumb"));
//trie.insertWord("dumb");
//System.out.println(trie.searchWord("dumb"));
//trie.deleteWord("dumb");
//System.out.println(trie.searchWord("dumb"));
}
}