前缀树的结构
上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:
①根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
②从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
③每个节点的所有子节点包含的字符互不相同。
④从第一字符开始有连续重复的字符只占用一个节点,比如上面的to,和ten,中重复的单词t只占用了一个节点。
前缀树的应用
1、前缀匹配
2、字符串检索
3、词频统计
4、字符串排序
下面看看怎样使用前缀树来实现前缀匹配的。
前缀匹配
了解了前缀树的结构后,就可以利用前缀树的性质来解决现实中的问题。比如说查找一个字符串数组中是否含有前缀单词,什么是前缀单词:上面的 in,就是 inn 的前缀单词。如果有十几万条单词,并且每个单词的长度都是5-10以内,这样必定存在大量重复的字符,因此利用前缀树来求解不仅速度快而且空间复杂度也比较好。
①定义前缀树结构
class TrieNode{
private TrieNode[] links;
private boolean isEnd;
private final int R=26;
private TrieNode root;
/** Initialize your data structure here. */
public TrieNode() {
links=new TrieNode[R];
}
public boolean isContainsKey(char ch){
return links[ch-'a']!=null;
}
public TrieNode get(char ch){
return links[ch-'a'];
}
public void put(char ch,TrieNode node){
links[ch-'a']=node;
}
public void setEnd(){
isEnd=true;
}
public boolean isEnd(){
return isEnd;
}
}
②建立前缀树
public class Trie {
private TrieNode root;
public Trie(){
root=new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node=root;
for(int i=0;i<word.length();i++){
char currentword=word.charAt(i);
if(!node.isContainsKey(currentword)){
node.put(currentword,new TrieNode());
}
node=node.get(currentword);
}
node.setEnd();
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node=searchPrefix(word);
return node!=null&&node.isEnd();
}
private TrieNode searchPrefix(String word){
TrieNode node=root;
for(int i=0;i<word.length();i++){
char curLetter=word.charAt(i);
if(node.isContainsKey(curLetter)){
node=node.get(curLetter);
}else{
return null;
}
}
return node;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node=searchPrefix(prefix);
return node!=null;
}