[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie)

 

트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다.

 

2. 트라이(Trie) 동작 원리

먼저 그림을 통해 살펴보도록 하겠습니다.

다음 그림은 문자열 {"jade", "japp", "an", "answer"}를 트라이(Trie)로 구현한 것입니다.

 

 

3. 트라이(Trie) 구현

트라이의 노드는 자손 노드를 가리키는 포인터 배열과, 문자열의 끝인지를 나타내는 bool 변수로 구성되어 있습니다.

보통 영어 소문자로만 이루어딘 경우가 대부분이기 때문에 배열의 크기를 26으로 선언합니다.

동적으로 메모리를 할당하기 때문에 delete로 해제해주는 것이 매우 중요합니다.

이제 문자열을 트라이에 넣어주는 함수에 대해 알아보겠습니다.

이미 트라이에 해당 문자에 해당하는 노드가 있다면 따라가고, 그렇지 않다면 새로 만들어줍니다.

문자열의 끝에 도달하면 end의 값을 true로 바꾸어줍니다.

마지막으로 트라이에서 찾고자 하는 문자열이 있는지 탐색하는 함수에 대해 알아보겠습니다.

만약 다음 문자로 가는 노드가 존재하지 않는다면 존재하지 않는 단어입니다.

또한, 문자열의 끝에 도달했을 때 end의 값이 true가 아니라면 존재하지 않는 단어입니다.

 

[ 소스코드 ]

struct trie {
    trie* ch[26];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) ch[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete ch[i];
        }
    }
 
    void insert(const char* c) {
        if (!*c) {
            this->end = true;
            return;
        }
 
        int now = *c - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(c + 1);
    }
 
    bool find(const char* c) {
        if (!*c || end) {
            return true;
        }
 
        int now = *c - '0';
        if (!num[now]) return false;
        return num[now]->find(c + 1);
    }
};