[AL] 9. 자료구조 (Trie)

9. 자료구조 (Trie)

1. 트라이(Trie)
2. 구현 방법

 

1. 트라이(Trie)

1.1. 개념

트라이(Trie) 는 Retireval(탐색) 에서 나온 단어이며, 문자열에서의 검색을 빠르게 해주는 자료구조이다.

만약 정수형에서 BST 를 이용한다면 O(logN) 의 시간만에 검색을 할 수 있다. 하지만 문자열에서 BST 를 사용한다고 할 때, 문자열의 길이가 M 이라면 O(M logN) 의 시간 복잡도를 갖는다.

이 때, 트라이를 이용한다면 O(M) 의 시간만에 원하는 문자열을 검색할 수 있게 된다!

 

1.2. 예시

우선 문자열 5개 {"blog", "he", "her", "supreme", "superm"} 이 있다고 가정해보자. 트라이는 이때 아래와 같은 트리를 형성하게 된다.

루트 노드가 되는 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

superm 은 s → su → sup → supe → super → superm 으로 이루어지는데 이 과정에서 나타난 것들은 모두 superm 의 접두사이다.

 

1.3. 트라이의 단점

트라이는 공간 복잡도에서 치명적인 단점을 갖는다.

트라이에서 저러한 O(m)의 시간 복잡도가 나오기 위해서는 다음 문자를 가리키는 노드가 필요하다. 예를 들어, 알파벳에 대해 트리를 형성해야 한다면 a~z 인 총 26개의 포인터 배열을 가지고 있어야 한다.

즉, 최종 메모리는 O(포인터 크기 * 포인터 배열의 개수 * 트라이에 존재하는 총 노드의 수) 가 된다.

 

 

2. 구현 방법

2.1. 소스 코드 (C++)

struct Trie {
  bool finish;		// 끝나는 지점
  Trie* next[26];	// 알파벳 26개에 대한 트라이
  
  Tire() : 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 current = *key - 'A';
      if(next[current] == NULL){
        next[current] = new Trie();	// 탐색이 처음되는 지점일 경우 동적할당
      }
      next[current]->insert(key+1);	// 다음 문자 삽입
    }
  }
  
  Trie* find(const char* key){
    if(*key == '\0')
      return this;		// 문자열이 끝나는 위치를 반환
    
    int current = *key - 'A';
    if(next[current] == NULL)
      return NULL;		// 찾는 값이 존재하지 않음
    return next[current]->find(key+1);	// 다음 문자 탐색
  }
  
}

 

 

 

---

참고 자료

• https://www.crocus.co.kr/1053
• https://brunch.co.kr/@springboot/75