[Algorithm] Trie 자료구조

KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에 알아볼 내용은 Trie 자료구조입니다.

Trie 자료구조

문자열 집합, {AB, ACD, ACEF, ACEG, HB, HC} 에 대해 Trie 자료구조가 어떻게 그려지는지 살펴보도록 합시다.

Trie 자료구조

시작 부분이 같은 단어끼리 부모를 공유한다면, 다음과 같은 트리 모양을 얻을 수 있습니다. 이 트리에 대하여 탐색을 진행할 경우, 트리의 시간 복잡도는 O(H) (H 는 트리의 높이) 가 될 것입니다. 그리고 트리의 높이는 문자열 집합 중 가장 긴 문자열의 길이와 동일하기 때문에 Trie 자료구조를 사용하면 가장 긴 문자열의 길이를 M 이라 했을 때, O(M) 만에 문자열 검색이 가능합니다.

 

언제 사용해야 하지?

Trie 자료구조에 대해서 고려해야 할 부분은 단어의 길이와children 의 수입니다.단어의 길이는 시간복잡도에 직접적인 영향을 미치므로 단어의 길이가 너무 긴 문자열이 있을 경우 사용하기에 부적합 합니다. 또한 children 의 수 역시 탐색 시간에 많은 영향을 미칩니다. 알파벳의 경우, 최대 children 노드는 26개, 숫자의 경우 최대 children 노드는 10개가 되므로 이 정도의 수는 Trie 자료구조를 사용하는데 있어서 적당합니다.

 

C++ 로 구현

Trie 자료구조를 구현하기 위해서는 두 가지의 핵심적인 함수가 필요합니다. 새로운 문자열에 대해서 Trie 에 추가해주는 insert 함수와 구현된 자료구조에서 단어를 찾는 find 함수입니다.

기본적으로 알파벳 대문자 영단어에 대한 구현입니다.

insert 함수

void insert(const char* key) {
  if (*key == '\0')
    finish = true;  
  else {
    int curr = *key - 'A';
    if (next[curr] == NULL)
      next[curr] = new Trie();
    next[curr]->insert(key + 1);
  }
}

재귀적으로 문자열 전체를 순회하면서 문자열 끝에 다다르면 끝내게 됩니다. 만약 트리가 만들어져 있지 않다면 새로운 Trie 객체를 만들어 길을 이어나가는 방식입니다.

find 함수

bool find(const char* key) {
  if (*key == '\0')
    return false;
  if (finish)
    return true;
  int curr = *key - 'A';
  return next[curr]->find(key + 1);
}

위에 insert 함수에서 문자열이 끝나는 지점에 finish를 true 로 해주었습니다. 따라서 문자열이 아직 끝나지 않았는데 finish가 true 라면 true 를 return 하고 이는 문자열 간의 포함관계가 있다는 소리입니다.

 

struct Trie {
    bool finish;
    Trie* next[26];
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }
    void insert(const char* key) {
        if (*key == '\0')
            finish = true;
        else {
            int curr = *key - 'A';
            if (next[curr] == NULL)
                next[curr] = new Trie();
            next[curr]->insert(key + 1);
        }
    }
    Trie* find(const char* key) {
        if (*key == '\0')return this;
        int curr = *key - 'A';
        if (next[curr] == NULL)return NULL;
        return next[curr]->find(key + 1); 
    }
};

Trie 자료구조에 대한 전체적인 코드입니다.

 

아래는 Trie 자료구조를 사용하는 백준 문제입니다.

[C++] BAEKJOON 5052번 전화번호목록