Trie 알고리즘 - 문자열 탐색

Trie 알고리즘이란?

- retrieval의 약자로, 문자열 탐색에 특화된 자료구조

- 트리 자료 구조 중 하나로, Digital Tree/ Radix Tree/ Prefix Tree 라고도 불림

- 텍스트 자동완성 등에 쓰임

 

 

red, reo, riot, tae 라는 단어가 들어간 Trie 자료구조

루트 노드는 특정 문자를 의미하지 않고 자식 노드만 가지고 있고,

각각 노드는 자식 노드와 단어의 마지막인지를 표시하는 변수를 가지고 있다.

 

 

특징

- 정렬된 트리 구조

- 자식 노드를 맵 형태<Key, Value>로 가지고 있음 (Key-알파벳, Value-해당하는 자식)

- 루트를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다

ex. R->E의 자식 D,O는 RE라는 공통 접두어를 가짐

 

 

---

 

Trie 알고리즘 구현 (Java)

 

1.먼저 TrieNode 를 만들어준다

class TrieNode{
    HashMap<Character, TrieNode> childNodes = new HashMap<>();
    boolean isLastChar;
    
    HashMap<Character,TrieNode> getChild(){
        return this.childNodes;
    }
    
    boolean getIsLastChar(){
        return isLastChar;
    }
    
    void setIsLastChar(boolean isLast){
        this.isLastChar = isLast;
    }
}

- 자식노드를 가리킬 Map과 마지막 글자인지를 표시하는 변수

- 각각의 getter/setter

 

2.Trie 클래스 구현

class Trie {
    TrieNode root;
    
    Trie(){
        root = new TrieNode();
    }
    
    void insert(String str){
        TrieNode current = this.root;
        
        for(char c : str.toCharArray()){           
            //자식노드로 계속 넘어가면서 없으면 생성
            current = current.getChild().computeIfAbsent(c, f-> new TrieNode());
        }
        
        //마지막 글자에는 마지막 표시
        current.setIsLastChar(true);
    }
    
    //해당 문자열이 트라이 자료구조에 있는지 탐색
    boolean search(String str){
        TrieNode current = this.root;
        
        for(char c : str.toCharArray()){
            current = current.getChild().get(c);  
            
            //해당 문자 없으면 false
            if(current == null){
            	return false;
            }
        }  
        
        //현재 노드가 단어의 끝인지 검사
        if(current.getIsLastChar()) return true;
        return false;
    }
}

- insert() 메소드로 문자 하나씩 저장 후, 마지막 글자엔 isLastChar = true;

- search() 메소드로 해당 문자열이 자료구조 안에 있는지 탐색