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;
	}
	}