Trie 자료구조

길이 L 짜리 문자열이 N개 담긴 list 에서 특정 문자열을 검색하는 시간복잡도가 어떻게될까?

이진탐색을 쓴다면 O(log N) 처럼 보이지만, 두 문자열을 비교하는 strcmp 함수의 시간복잡도가 O(L) 이기에,

전체 시간복잡도는 O(L log N) 이 된다. 심지어 list 가 정렬되어 있어야 한다. 

 

Trie 를 쓴다면, O(NL) 의 시간복잡도로 전처리를 하게 된다.

이후에는 어떤 문자열이 오더라도 O(L) 만에 list 에서 검색이 가능하다.

 

BOJ 5670 휴대폰 자판을 예시로 들어보자.

hell, hello, heaven, goodbye 4개의 문자열이 들어온다.

hell 이 먼저 들어오니까 이 때의 Trie 를 그림으로 확인해보자.

---

 

0. 초기 상태

루트만 있는 Trie

Trie의 초기 상태. 루트 노드만 존재한다.

---

1. 'h' 삽입

'h' 가 삽입된 Trie

첫 글자인 'h' 가 들어온 상태다.

---

2. 'e' 삽입

'he' 가 삽입된 Trie

두 번째 글자 'e' 는 'h' 노드 밑에 붙어 'he'가 된다.

---

 

3. 'l' 삽입

'hel' 이 삽입된 Trie

---

4. 'l' 삽입

'hell' 단어가 다 삽입된 Trie

hell 의 네 번째 글자까지 다 삽입된 상태.

이 때 추가된 노드는 hell 의 끝부분이다.

때문에, 여기서 단어가 끝난다고 표시해주어야 한다.

---

5. 'hello' 삽입

'hello' 까지 삽입된 Trie

뒤이어 "hello" 가 삽입된다고 해보자.

h, he, hel, hell 까지는 노드 추가 없이 그대로 따라간다.

여기서 'o' 만 hell 노드 밑에 붙여주면 된다.

물론 단어의 끝 표시도 해주어야 할 것이다.

---

6. 최종 Trie

최종 Trie

뒤이어 heaven, goodbye 까지 삽입한 상태다.

어렵지 않게 이해할 수 있다.

 

 

Trie 를 보면 기본적으로 최대 26진 트리의 형태다. ( 소문자로만 구성되었다고 가정할 때 )

또한 트리의 깊이는 최대 L, 즉 문자열의 길이다.

따라서 우리는 O(L) 만에 트리를 따라가면서 문자열이 있는지 검색이 가능하다.

 

이를 어떻게 구현하면 될까? 아래는 나의 초기 코드다. (아직은 개선될 여지가 많아 보임)

 

struct Trie{
    bool finished; int cnt;
    Trie* child[26];
    Trie(){
        finished = false; cnt = 0;
        for(int i=0;i<26;i++){
            child[i] = NULL;
        }
    }
    ~Trie(){
        for(int i=0;i<26;i++) delete child[i];
    }
    void inserts(Trie* now, char* str, int idx, int len){
        if(idx >= len){
            now->finished = true;
            return;
        }
        if(now->child[str[idx]-'a'] == NULL){
            now->child[str[idx]-'a'] = new Trie();
            now->cnt++;
        }
        inserts(now->child[str[idx]-'a'], str, idx+1, len);
    }
    void search_(Trie *now, char* str, int idx, int len){
        if(idx >= len){
            if(now->finished == true) printf("%s Found\n", str);
            return;
        }
        if(now->child[str[idx]-'a'] == NULL) return;
        search_(now->child[str[idx]-'a'], str, idx+1, len);
    }
};

이제 이를 분석해보자.

 

bool finished; int cnt;
Trie* child[26];

Trie 구조체 안에 들어가는 원소들이다.

finished : 해당 노드가 단어의 끝 지점인지, 아닌지 나타내는 boolean 이다.

cnt : 해당 노드의 자식이 몇 개인지에 관한 변수다.

child[26] : Trie 포인터 배열로, 최대 26개의 자식이 있기 때문에 배열 크기가 26이다. (다 소문자라는 가정)

 

Trie(){
    finished = false; cnt = 0;
    for(int i=0;i<26;i++){
        child[i] = NULL;
    }
}
~Trie(){
    for(int i=0;i<26;i++) delete child[i];
}

생성자와 소멸자이다.

생성자를 보면 child 들을 다 nullptr 로 만들어준다. 갓 생성되어 자식이 없기 때문에 당연하다.

소멸자를 보면 child 들을 다 delete 시킨다.

 

void inserts(Trie* now, char* str, int idx, int len){
    if(idx >= len){
        now->finished = true;
        return;
    }
    if(now->child[str[idx]-'a'] == NULL){
        now->child[str[idx]-'a'] = new Trie();
        now->cnt++;
    }
    inserts(now->child[str[idx]-'a'], str, idx+1, len);
}

Str 이라는 문자열을 Trie 에 삽입하는 함수다.

idx 가 Str 의 길이, 즉 len 이상이 되면 단어의 끝에 도달했다는 뜻이므로 그 지점의 finished 를 true 로 한다.

 

그렇지 않다면, 노드를 추가할지 기존의 노드를 쓸지 결정해야 한다.

만약 idx 번째 글자에 해당하는 노드가 만들어져 있지 않다면 (NULL), 우리는 새로운 노드를 만들어주어야 한다.

new Trie(); 가 그 역할을 한다.

자식이 새로 생긴 것이므로 now 의 cnt 도 1 증가 시키면 된다.

 

하지만 idx 번째 글자에 해당하는 노드가 이미 만들어져 있다면 그 노드를 호출하여 따라가 주면 된다.

 

void search_(Trie *now, char* str, int idx, int len){
    if(idx >= len){
        if(now->finished == true) printf("%s Found\n", str);
        return;
    }
    if(now->child[str[idx]-'a'] == NULL) return;
    search_(now->child[str[idx]-'a'], str, idx+1, len);
}

Str 라는 문자열이 Trie 에 있는지 확인하는 함수다.

만약 idx 가 len 을 넘어가면 단어가 끝났다는 것이다.

 

그런데 이 지점의 finished 가 false 라면, Trie 에서 검색은 되지만 등록은 안 되어 있다는 뜻이다.

예를 들어, Trie 에 "princess" 만 들어갔을 때 "prince" 는 검색은 될 것이지만, 등록은 안 되어 있어야 한다.

 

idx가 len을 넘어가지 않을 때, 즉 Str[idx] 가 유효할 때를 보자.

만약 Str[idx] 에 해당하는 노드가 없다면, 즉 NULL 라면, 이 단어는 Trie 에 등록이 안 되어 있다는 뜻이다.

그렇지 않으면 아직은 더 따라가 볼 여지가 있으므로 그 노드로 가면 된다.