[CS 스터디: JAVA] (6) 트라이

트라이(Trie) 

: 문자열 집합을 저장하고 탐색하기 위한 트리 형태의 자료 구조

: 자동완성 기능, 사전 검색등에 특화되어 있는 구조(단어의 앞글자부터 찾는)

   -- 예를 들어, "bear" 을 찾을 때 'b' 를 찾고 'e','a','r'를 순서대로 찾는다.

 

 

>> bell, bear, bore, bat, ball, stop, stock, stack을 저장한 트라이 트리 구조 

 

 

→ Trie 구조의 특징

(1) 항상 루트 노드는 null 노드 (여러개 집합의 문자열을 저장해야 하므로)

(2) 각각의 자식 노드들은 알파벳 순서대로 정렬

(3) 각각의 노드는 최대 26개의 자식을 가질 수 있음(A부터 Z까지)

(4) 루트 노드를 제외한 각각의 노드는 1개의 알파벳 노드를 저장할 수 있음

(5) 삽입하는 가장 긴 문자열의 길이가 L일 때, 탐색 시간 복잡도는 O(L)

 

 

→ Java 구현

 

public class Trie {
    static final int ALPHABET_SIZE = 26;
      
    static class TrieNode{
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
       
        boolean isEndOfWord; // 만약 노드가 단어의 끝이라면 true
          
        TrieNode(){
            isEndOfWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };
       
    static TrieNode root; 
      
    static void insert(String key){	// 키 삽입 
        int level;
        int length = key.length();
        int index;
       
        TrieNode pCrawl = root;
       
        for (level = 0; level < length; level++)
        {
            index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
       
            pCrawl = pCrawl.children[index];
        }
       
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }
       
    static boolean search(String key){ // 키 탐색(존재시 true, 미존재시 false)
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;
       
        for (level = 0; level < length; level++){
            index = key.charAt(level) - 'a';
       
            if (pCrawl.children[index] == null)
                return false;
       
            pCrawl = pCrawl.children[index];
        }
       
        return (pCrawl.isEndOfWord);
    }
       
    public static void main(String args[]){
        String keys[] = {"the", "a", "there", "answer", "any",
                         "by", "bye", "their"}; // 추가할 키 목록
       
        root = new TrieNode();
       
        int i;
        for (i = 0; i < keys.length ; i++)
            insert(keys[i]);	//	트리 생성
    }
}