[알고리즘 개념 정리] Trie 알고리즘

 

[알고리즘 개념 정리] Trie 알고리즘

 

Trie란?

• Trie : 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.
• DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다.

 

사용목적

• 문자열을 탐색할 때 하나하나씩 비교하는 방법보다 효율적이기 때문.
• 하지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음
• 실제 사용 예시로는 검색어 자동완성, 사전에서 찾기, 문자열 검사 등에서 사용한다.

 

시간 복잡도

• 제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M 이라 할 때 시간 복잡도는 아래와 같다.
  • 생성시 시간복잡도 : O(M*L) ⇒ 모든 문자열들을 넣어야 하니 M 개에 대해서 트라이 자료구조에 넣는것은 가장 긴 문자열 길이만큼 걸리니 L 만큼 걸려서 O(M*L) 만큼 걸린다. 물론 삽입 자체만은 O(L) 만큼 걸린다.
  • 탐색시 시간복잡도 : O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L) 만큼 걸린다.

 

코드 구현

#include <iostream>
#include <string>
#include <cstring>

#define ALPHABETS 26

int char_to_index(char c) {
    return c - 'A';
}

struct Trie {
    bool is_terminal;
    Trie* children[ALPHABETS];
    
    // Constructor
    Trie() : is_terminal(false) {
        memset(children, 0, sizeof(children));
    }
    
    // Delete all children (Destructor)
    ~Trie() {
        for(int i = 0; i < ALPHABETS; ++i) {
            if(children[i]) delete children[i];
        }
    }
    
    void insert(const char* key) {
        if(*key == '\0') {
            is_terminal = true;
        } else {
            int index = char_to_index(*key);
            
            if(children[index] == 0)
                children[index] = new Trie();
            
            children[index] -> insert(key + 1);
        }
    }
    
    Trie* find(const char* key) {
        if(*key == 0) {
            return this;
        }
        
        int index = char_to_index(*key);
        if(children[index] == 0) {
            return NULL;
        }
        
        return children[index]->find(key + 1);
    }
    
    bool string_exist(const char* key) {
        if(*key == 0 && is_terminal) {
            return true;
        }
        
        int index = char_to_index(*key);
        if(children[index] == 0)
            return false;
        
        return children[index] -> string_exist(key+1);
    }
};

 

코드 설명

• int char_toIndex(char c) : 알파벳 대문자 기준
• is_terminal : 단어의 끝임을 표시하는 변수
• void insert(const char* key) : 새로운 문자열을 트라이에 추가하는 코드
• Trie* find(const char* key) : key에 해당하는 문자열을 접두어로 가지고 있는지 확인하고 가지고 있다면 해당 접두어가 끝나는 부분의 위치를 반환
• bool string_exist(const char* key) : key에 해당하는 문자열이 포함되어 있는지 확인하는 코드. 해당 key의 문자열이 있다면 true를 반환하고 없으면 false 반환

---

Reference

• https://twpower.github.io/187-trie-concept-and-basic-problem