[알고리즘] 트라이(Trie) 개요 및 개념

여러 개의 문자열이 등록된 사전을 만들고 특정 문자열이 이 사전안에 등재된 문자열인지 확인하려면 어떻게 해야할까요?
단순히 일일이 비교해서 확인해보면 되지만 이 경우 최악의 경우에 \( O(nm) \)의 수행시간이 필요합니다.
혹은 이진 탐색을 사용하여 \( O(m\textbf{log}n) \)으로 단축시킬 수 있지만 정렬 과정에서 \( O(mn\textbf{log}n) \)의 시간이 걸리게 됩니다.
이러한 문자열 검색의 시간복잡도를 단축시키기 위해서는 프레드킨이 명명한 Retrieval Tree 알고리즘이 필요합니다. (Prefix Tree, Digital Search Tree 라고도 합니다.)

트라이(Trie)란?

트라이는 탐색 트리의 일종으로 문자열을 빠르게 검색할 수 있는 자료 구조입니다.
K진 트리의 구조를 갖고 있으며 단어 사전을 트라이로 생성한 후에 찾을 단어를 다시 트라이를 사용하여 검색합니다.

트라이 구조 (출처 : 위키백과)

위 그림과 같이 트라이의 Root 노드는 항상 공백 문자열을 가지고 있으며 빈 문자열 상태를 의미합니다.

그리고 문자가 추가되면 해당되는 접두사에 따라 분기되어 자식 노드로 저장 됨을 알 수 있습니다.

트라이 구현 (C++)

그렇다면 트라이 노드를 C++ 언어로 설계해 보겠습니다. 트라이노드 구조체 안에 삽입과 검색 함수를 함께 구현할 수도 있지만 저는 따로 구현해보았습니다.

트라이 노드

트라이 트리의 노드를 struct로 구현한 코드입니다.

struct TrieNode{
    TrieNode* children[26]; // 알파벳 26개의 대한 배열
    bool isEnd; // 문자열의 종료 지점인지 확인
    
    TrieNode():isEnd(false){
        memset(children, 0, sizeof(children));
    }

    ~TrieNode(){
        for(int i=0; i<26; i++){
            if(children[i]) delete children[i];
        }
    }
};

트라이 삽입

트라이 트리에 주어진 문자열을 삽입하여 사전을 생성하는 코드입니다.

void insert(string word) {
    TrieNode* current = &root; // root 트라이노드는 전역변수로 선언
    for(int i=0; i<word.length(); i++){
        int wordIndex = word[i] - 'a';
        if (current->children[wordIndex] == NULL){
            current->children[wordIndex] = new TrieNode();
        }
        current = current->children[wordIndex];
    }
    current->isEnd = true;
}

트라이 검색

트라이 트리로 구현된 사전에 원하는 문자열이 속해있는지 검색하는 코드입니다. 트라이 삽입 코드와 비슷합니다.

bool search(string word) {
    TrieNode* current = &root; // root 트라이노드는 전역변수로 선언
    for (int i=0; i<word.length(); i++){
        int wordIndex = word[i] - 'a'; // 사전이 대문자일 경우 'A'
        if (current->children[wordIndex] == NULL){
            return false;
        }
        current = current->children[wordIndex];
    }
    if (current->isEnd) return true; // 문자열의 끝이 맞는 경우 true 반환
    else return false;
}

시간복잡도

이제 본 트라이 알고리즘의 시간복잡도를 확인해보겠습니다.
문자열의 길이가 \( m \)인 문자열 \( n \)개를 삽입할 경우에는 \( O(mn) \)의 시간복잡도가 발생합니다. 삽입 연산 자체는 \( O(m) \)의 시간복잡도가 되겠습니다.

문자열의 길이가 \( m \)인 문자열을 검색할 경우에는 역시 삽입과 마찬가지로 \( O(m) \)의 시간복잡도가 되겠습니다. 

단점

이렇게 문자열 탐색의 시간복잡도를 크게 압축한 트라이 알고리즘에도 단점이 존재합니다. 바로 문자열이 매우 길어지면 그에 따라 차지하는 메모리 공간도 매우 커진다는 것입니다. 각 접두사마다 대(소)문자를 가진 포인터 배열을 26개씩 가지게 되는데 만약 접두사를 전혀 공유하지 않는 문자열들이 이 트리안에 저장된다면 엄청나게 많은 메모리를 필요로하게 됩니다.

결론

여러개의 문자열을 효과적으로 사전형태로 구현하고 다시 탐색 및 검색하기 위해서는 완전탐색, 이진탐색보다 트라이 트리를 구현하여 탐색하는 것이 매우 시간적으로 매우 효과적임을 배웠습니다. 하지만 공간복잡도 면에서는 많은 메모리 공간을 차지하게 되지만 문제 해결시에 이러한 조건들이 오히려 힌트로 작용할 수도 있을 것 같습니다. (여유로운 메모리 제한 제시 또는 문자열 길이 제한 제시)

트라이 알고리즘에 대한 개념 자체는 크게 어려운 점이 없었으나 막상 문제를 풀려고 할때 노드를 사용하여 K진 자료구조 자체를 구현하는 것이 쉽게 떠올리기에 힘든 점이 있는 것 같습니다.
다음 포스팅에서는 트라이 알고리즘을 사용한 예제 문제들을 살펴보고 풀이하겠습니다.