트라이 (Trie) 자료구조

미루고 미뤘던 자료구조, 이번 기회에 트라이에 대해서 공부하게 됐다.

내가 여러 사이트를 검색하면서 공부한 것을 정리했다.

트라이(Trie) 자료구조란?

 

쉽게 생각해서 문자열을 빠르게 탐색할 수 있는 자료구조다.

얼마나 빠르길래 이렇게 따로 명칭까지 있는 것일까?

 

결론부터 말하자면 M이 최대 문자열의 길이라고 했을 때, O(M)만에 검색할 수 있다.

 

트라이를 표현하는 특징은 여러 가지가 있다.

1) 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리구조

2) 루트에서부터 내려가면서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다.

3) 문자열 트리 구조

 

트라이 작동 원리

 

트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드를 생성해가면서 만들어진다.

이 과정에서는 반복적으로 재귀 호출이 일어나게 된다.

1. 주어진 문자열에서 현재 문자를 가져온다.
2. 현재 문자로 이루어진 노드를 확인한다.
   1. 만약 노드가 존재한다면, 그 노드로부터 다음 문자열을 탐색하러 간다.
   2. 만약 노드가 없다면, 노드를 새로 만들고, 해당 노드를 통해 다음 문자열을 탐색한다.
3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다.

삽입하는 과정이면,

해당 문자열이 "ABC"라고 해보자.

루트 노드로부터 ABC 문자열에서 문자 A를 검색한다.

문자 노드 A가 있으면 그 아래 자식 노드를 검색하러 가고, 없으면 새롭게 A라는 노드를 만든다.

문자 노드 B가 있으면 그 아래 자식 노드를 검색하러 가고, 없으면 새롭게 B라는 노드를 만든다.

이렇게 쭉 가다가 C가 끝나고 그다음을 확인해보니까 문자열의 끝인 널문자에 도달하게 됐다.

만약에 ABC라는 문자열을 트라이에 저장했다고 한다면 그 끝을 표현하는 Bool 변수를 true로 만들어주면 된다.

 

검색하는 과정이라면,

해당 문자열에 앞에서부터 문자를 하나씩 살펴보면서 해당 문자가 노드가 없으면 false고,

있다면 그 문자에 연결된 다음 자식 노드를 확인해보러 가면 된다.

 

트라이 자료구조 장/단점

 

장점은 문자열을 빠르게 찾을 수 있다.

여기서 빠르게 찾는다는 것은 탐색과 삽입이 모두 O(M)에 이루어진다.

왜? 트라이에서 검색을 할 경우에 최대 트리의 높이까지 탐색하게 되는데,

이때 시간 복잡도는 O(H)이지만, 트리의 높이가 결국 최대 문자열의 길이가 되기 때문에 결국 O(M)에 가능하다.

 

어떻게 삽입하든 간에 트라이가 구성된 트리는 항상 똑같다. 이는 자동으로 정렬된 효과를 볼 수 있다.

왜냐하면 A로 시작하는 문자열은 A라는 노드 아래로 쭉 이어진 서브 트리를 이루는 형태이기 때문이다.

 

단점은 공간 복잡도가 매우 크다. 빠르면 대가가 있다.(trade-off 관계)

숫자에 대한 트라이를 만든다면 0~9인 총 10개의 포인터 배열 선언 + 문자열의 끝을 의미하는 bool

알파벳에 대한 트라이를 만든다면 a~z인 총 26개의 포인터 배열 선언 + 문자열의 끝을 의미하는 bool

 

최종적으로 메모리는 [포인터 크기 x 포인터 배열 개수 x 트라이에 존재하는 총노드의 개수]

 

아니 map을 이용하면 트라이랑 비슷하지 않을까?

 

우리가 배운 map은 red-black tree 구조인 균형 이진 탐색 트리다.

어떤 자료를 검색할 때 O(logN)이 걸린다는 것을 안다.

 

그런데 생각해보자.

여러 개의 문자열 중에서 우리가 찾는 문자열을 검색하는 시간은 O(logN x M)이다.

왜? 여러 개의 문자열 N에서 우리가 찾고자 하는 문자열의 길이가 M이기 때문이다.

 

그런데 트라이는?

O(M)만에 끝내버린다.

 

어떻게 구현할까?

 

다른 알고리즘처럼 틀이 존재한다.

트라이는 자료구조이기 때문에 입맛에 맞게 변형하여 사용하면 된다.

다만 이것을 어떻게 활용할지는 우리에게 달렸다.

#include <iostream>
#include <string>

using namespace std;

//트라이를 구성하는 노드는 자손 노드를 가리키는 포인터 목록과 문자열의 끝인지를 나타내는 변수로 구성된다.
struct Trie
{
    Trie* ch[26]; //26가지 알파벳에 대한 트라이
    bool end;     //끝나는 지점을 표시해줌
    
    //문자열을 트라이에 넣어주는 함수
    void insert(const char* s)
    {
        //문자열 끝에 도달하는 경우
        if(*s == '\0')
        {
            this->end = true;
            return;
        }
        
        //현재 문자가 노드에 있으면 넘어가고, 아니라면 새롭게 하나 만들어주고 넘어간다.
        int now = *s - 'A';
        if(!ch[now]) ch[now] = new Trie();
        ch[now]->insert(s + 1);
    }
    
    bool find(const char* s)
    {
        //문자열 끝에 도달했을 때
        if(*s == '\0')
        {
            //문자열의 끝이라면 찾은 것이고, 아니라면 탐색에 실패
            if(end) return true;
            return false;
        }
        //다음으로 가는 노드가 있으면 다음으로 가고, 아니라면 탐색에 실패
        int now = *s - 'A';
        if(!ch[now]) return false;
        return ch[now]->find(s + 1);
    }
    
    Trie() : end(false)
    {
        for(int i = 0; i < 26; i++)
            ch[i] = nullptr;
    }
    ~Trie()
    {
        for(int i = 0; i < 26; i++)
        {
         if(ch[i])
             delete ch[i];
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    Trie* root = new Trie();
    string s;
    cin >> s;
    root->insert(s.c_str());
    string temp = "AAA";
    if(root->find(temp.c_str()))
        cout << "find!\n";
    else
        cout << "No\n";
    
    delete root;
    return 0;
}