[자료구조] Trie

📌 트라이(Trie)

문자열에서 검색을 빠르게 도와주는 자료구조

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.

• 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다.

• 예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다.

정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN)
하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다.

따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다.

트라이를 활용하면? → O(M)으로 문자열 검색이 가능함!

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다.

📌 트라이의 장단점

장점

트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다.

더불어, 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에

문자열의 추가와 탐색 모두 O(M)만에 가능하다.

단점

트라이의 단점은 필요한 메모리의 크기가 너무 크다는 점이다.

문자열이 모두 영소문자로 이루어져 있다고 해도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다.

최악의 경우에는 집합에 포함되는 문자열들의 길이의 총합만큼 노드가 필요하므로, 총메모리는

O(포인터 크기 포인터 배열 개수 총노드의 개수)가 된다.

만약, 1000자리의 문자열이 1000개만 들어온다고 하더라도 100만 개의 노드가 필요하고, 포인터의 크기가 8byte라고 하면 약 200MB의 메모리가 필요하게 된다.

즉, 이 단점을 해결하기 위해서 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 꽤나 까다롭다.

또한, 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다.

📌 트라이의 구현 예제

문제에서 Trie를 java로 구현한 코드

static class Trie {
    boolean end;
    boolean pass;
    Trie[] child;

    Trie() {
        end = false;
        pass = false;
        child = new Trie[10];
    }

    public boolean insert(String str, int idx) {

        //끝나는 단어 있으면 false 종료
        if(end) return false;

        //idx가 str만큼 왔을때
        if(idx == str.length()) {
            end = true;
            if(pass) return false; // 더 지나가는 단어 있으면 false 종료
            else return true;
        }
        //아직 안왔을 때
        else {
            int next = str.charAt(idx) - '0';
            if(child[next] == null) {
                child[next] = new Trie();
                pass = true;
            }
            return child[next].insert(str, idx+1);
        }

    }
}

출처
출처
출처