Trie(트라이)-자료구조

trie 혹은 prefix tree라 함은, 주로 스트링을 가지는 동적 셋 혹은 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조를 의미한다. 이진 검색 트리와는 다르게, 트리상에서의 노드들은 그 노드와 연관된 키를 저장하지 않는다. 이 대신, 트리상에서의 위치가 현재의 키를 나타낸다.  특정 노드의 모든 후손들은 그 노드에서와 동일한 prefix를 가지며, 루트 노드는 빈 문자열을 갖는다. 값은 모든 노드에서 존재하는 것이 아니고, 말단 노드(leaves) 혹은 특정 키에 해당하는  내부(inner) 노드에서만 존재한다. prefix tree의 공간사용을 최적화 하기 위하여, compact prefix tree가 구상되었다. trie라는 단어는 reTrieval이라는 단어에서 유래하였다.

• Trie를 왜 사용해야 하는가?

많은 양의 텍스트정보를 빠르고 효율적으로 검색하기 위해 그래서 Trie는 사전 혹은 인터넷 자동완성의 retrieval을 효과적으로 할 수 있는 자료구조이다.

• Trie의 특성

키워드 정보는 마지막 노드만 가지고 있고 나머지 노드들은 정보는 없고 링크만 가지게 된다.

시간복잡도

이진 검색 트리   O (logn)

문자열 이진 검색 트리  O(Mlogn)

트라이  O(M)

• 문자열은 정수와 실수와는 달리 그 길이가 변하기 대문에 검색에 시간이 많이 걸린다
• 길이가 고정된 정수나 실수의 경우 이진 트리에서 O(logn) -> 이진 트리에서는 한 번 검색할 때마다 대상이 반으로 줄기 때문
• 문자열은 길이가 변하기 때문에 문자열의 최대 길이 M을 곱한 O(MlogN)이 된다.

class TrieNode {
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean isLeaf;
 
    public TrieNode() {}
 
    public TrieNode(char c){
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    public void insert(String word) {
        HashMap<Character, TrieNode> children = root.children;
 
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
 
            TrieNode t;
            if(children.containsKey(c)){
                    t = children.get(c);
            }else{
                t = new TrieNode(c);
                children.put(c, t);
            }
 
            children = t.children;
 
            //set leaf node
            if(i==word.length()-1)
                t.isLeaf = true;    
        }
    }
 
    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode t = searchNode(word);
 
        if(t != null && t.isLeaf) 
            return true;
        else
            return false;
    }
 
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if(searchNode(prefix) == null) 
            return false;
        else
            return true;
    }
 
    public TrieNode searchNode(String str){
        Map<Character, TrieNode> children = root.children; 
        TrieNode t = null;
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(children.containsKey(c)){
                t = children.get(c);
                children = t.children;
            }else{
                return null;
            }
        }
 
        return t;
    }
}