트라이 (Trie) - 비선형 자료구조

👩‍💻  트라이 (Trie)

문자열을 저장하고 빠르게 탐색하기 위한 정렬된 트리 형태의 자료구조

문자열 저장을 위한 메모리가 필요하지만, 탐색이 빠름 ***

 

✏️ 시간 복잡도 및 생성 복잡도

길이가 N인 문자열 탐색의 시간 복잡도 :O(N)

생성 복잡도 : O(MN) (M: 문자열 개수)

 

✏️ 트라이 형태

문자열 구성 ex) apple, april, ace, bear, best

 

✏️ 트라이의 삽입

앞서 있는 것과 비교하여 있는 부분은 그대로 따라가서 없는 부분부터 노드를 생성, 문자의 끝 노드는 따로 표기를 해둔다.

 

✏️ 트라이의 삭제

문자를 따라가서 끝쪽에 다다르면, (<ex> apple에서의 e, app에서의 p ) 

• 해당 칠해져있는 노드의 (문자열 끝 노드의) 자식노드가 없으면 색칠한 것을 없앤 후 위로 이동,
  그 다음 노드가 자식노드가 없고, 흰색 노드 (끝 노드가 아니라면) 지운 후 위로 올라가 자식노드가 있거나 끝 노드 일때까지 반복한다.
• 만약 문자열의 끝 노드 아래 자식노드가 더 존재한다면 해당 노드의 색만 흰색으로 다시 바꿔주면 된다.

 

✏️ 트라이의 구현

✨ Key, Value로 이루어진 노드로 구성

• Key : 알파벳
• Value : 자식 노드 

Class Noe{
    HashMap<Character, Node> child;
    boolean isTerminal; // 현재 Node가 단어의 끝 노드인지 
}

 

✨ Java에서 Trie 구현

Class Node{
	HashMap<Character, Node> child;
    boolean isTerminal;
    
    public Node(){
    	this.child = new HashMap<>();
        this.isTerminal = false;
    }
}

Class Trie{
	Node root;
    public Trie(){
    	this.root = new Node();
    }
    
    // 삽입
    public void insert(String str){
    	Node cur = this.root;
        
        for(int i=0; i < str.length(); i++){
        	char c = str.charAt(i);
            
            // *** HashMap<>()에 저장된 메소드 putIfAbsent() 사용 *** 
            // c 가 cur기준으로 자식노드로 없으면 넣어주고, 있다면 넘어가게 된다.
            cur.child.putIfAbsent(c, new Node()); 
            
            cur = cur.child.get(c);
            
            if(i == str.length() - 1){
            	cur.isTerminal = true;
                return;
            }
        }
    }
    
    // 탐색
    public boolean search(String str){
    	Node cur = this.root;
        
        for(int i=0; i<str.length(); i++){
        	char c = str.charAt(i);
            
            if(cur.child.containsKey(c)){
            	cur = cur.child.get(c);
            }else{
            	return false;
            }
            
            if(i == str.length() - 1){
            	if(!cur.isTerminal){
                	return flse;
                }
            }
        }
        return true;
    }
    
    // 삭제
    public void delete(String str){
    	boolean ret = this.delete(this.root, str, 0);
        if(ret){
        	System.out.println(str + " 삭제 완료");
        }else{
        	System.out.println(str + " 단어가 없습니다.");
        }
    }
    
    public boolean delete(Node node, String str, int idx){
    	char c = str.charAt(idx);
        
        if(!node.child.containsKey(c)){
        	return false;
        }
        
        Node cur = node.child.get(c);
        
        idx++;
       
        if(idx == str.length()){
        	if(!cur.isTerminal){
            	return false;
            }
            // 단어의 끝 노드가 맞다면
            cur.isTerminal = false;
            
            if(cur.child.isEmpty()){ // 아래 딸린 자식노드들이 없다면,
            	node.child.remove(c);
            }
        }
        else{
        	if(!this.delete(cur, str, idx)){ // 재귀함수 진행 
            	return false;
            }
            if(!cur.isTerminal && cur.child.isEmpty()){ // 끝 문자도 아니고, 해당 노드에서 파생되는 문자도 없다면 같이 삭제
            	node.child.remove(c);
            }
        }
        return true;
    }
}