Trieクエリーツリー
1872 ワード
trieツリーの特徴:
メモリのスワップ時間、クエリの効率化
一、接点構造
二、木の生成
メモリのスワップ時間、クエリの効率化
一、接点構造
public class TreeNode {
char data;//
boolean isEnd;//
LinkedList<TreeNode>childList;//
int count;// ;
public TreeNode(char c){
this.data=c;
isEnd=false;
childList=new LinkedList<TreeNode>();
count=0;
}
//
public TreeNode subNode(char c){
if(childList!=null){
for(TreeNode t:childList){
if(t.data==c)return t;
}
}
return null;
}
}
二、木の生成
public class TrieTree {
//
private TreeNode root;
// root
public TrieTree(){
root=new TreeNode(' ');
}
public void insertNode(String word){
if(searchNode(word))return;
TreeNode current = root;
for(int i = 0; i < word.length(); i++){
TreeNode child = current.subNode(word.charAt(i));
if(child != null){
current = child;
} else {
current.childList.add(new TreeNode(word.charAt(i)));
current = current.subNode(word.charAt(i));
}
current.count++;
}
// Set isEnd to indicate end of the word
current.isEnd = true;
}
//
// root
public boolean searchNode(String word){
TreeNode tn=root;
for(int i=0;i<word.length();i++){
if(tn.subNode(word.charAt(i))==null){
return false;
}else{
tn=tn.subNode(word.charAt(i));
}
}
return tn.isEnd;
}
}