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

 

보통 우리가 많은 양의 정수, 실수형 배열에 대한 구간 합, 최대치 등을 구할 경우

구간 트리(세그먼트 트리, 펜윅 트리)를 만들어 O(log n) 만에 검색을 할 수 있게 된다.

 

하지만 문자열을 다룰 때에는 정수, 실수 등 크기가 정적인 변수들을 다루는 것과 좀 다른데

문자열의 경우 문자열 변수를 비교하는 데에 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문이다.

(정수처럼 한 번에 비교가 되는 자료형이 아니기 때문입니다.)

 

따라서 정수형 배열에서 원하는 원소를 찾을 때 O(log n)이 걸렸다면,

같은 알고리즘으로 원하는 문자열을 찾으려면 문자열의 길이 |S|을 곱한 O(|S| log n) 이 걸리게 된다.

 

이런 문제를 해결하기 위해 문자열을 찾는 문제에서 우리는 더 나은 자료 구조를 찾을 필요가 있고, 

대표적으로 "트라이(Trie)"를 사용한다.

 

 

 

1. 트라이(Trie) 란?

위와 같은 문제를 해결하기 위해 고안된 문제열 특화 자료 구조이다.

트라이는 문자열 집합을 표현하는 트리 자료 구조로 집합 내에서 원하는 원소를 찾는 작업을 O(|S|) 시간만에

할 수 있다.

 

먼저, 이해를 돕기 위해 트라이의 그림을 그려보았다.

 

 

문자열 배열 S = {"fre", "fri", "peo", "leg" }에 대한 트라이 모양이다.

 

그림을 보면, 트리의 루트부터 시작해 각 문자열의 트리를 꾸려나가는 것을 볼 수 있다.

 

트라이의 루트는 항상 길이가 0인 문자열에 대응되며

 

루트를 제외한 모든 노드는 모두 하나의 문자로 이루어져있긴 하지만

 

한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모-자식 관계로 연결된다.

 

즉 위 그림에서 'f' 와 'r'의 관계는, 문자열 "fri"에서 "fr"인 접두사를 얻을 수 있기 때문에 'f'는 'r'의 부모가 되는 것이다.

 

따라서 트리 노드의 깊이가 깊어질 때마다 문자열의 길이는 1씩 늘어난다.

 

색칠된 노드들은 종료 노드로, 이 노드들은 해당 위치에서 종료되는 문자열이 트라이가 표현하는 집합에 포함되어 있다는것을 나타낸다. ("fri", "peo" 등..)

 

따라서 우리는 트라이를 만들어 놓으면, 각각의 노드별로 대응되는 접두사들을 얻을 수 있게 되고,

 

각 노드마다 대응되는 문자열을 저장할 필요가 없다.(그래서 각 노드에 한 글자씩 있다!)

 

 

2. 트라이 기본 구현 코드

 

학교 교수님이 항상 말씀하시는 "백문이 불 여일 RUN"처럼일단 완성 코드를 보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'A'; }
//트라이의 한 노드를 나타내는 객체
struct TrieNode {
    TrieNode* children[ALPHABETS];
    //이 노드에서 종료하는 문자열의 번호. 없으면 -1
    int terminal;
    //이 노드를 루트로 하는 트라이에 가장 먼저 추가된 단어의 번호. -1로 초기화
    int first;
    TrieNode() : terminal(false) {
        memset(children, 0, sizeof(children));
        first = -1;
    }
    ~TrieNode() {
        for (int i = 0; i < ALPHABETS; i++) {
            if (children[i])
                delete children[i];
        }
    }
    //이 노드를 루트로 하는 트라이의 번호. id인 문자열 key를 추가한다.
    void insert(const char* key, int id) {
        //first를 우선 갱신
        if (first == -1) first = id;
        //문자열이 끝났다면 terminal만 바꾸고 종료
        if (*key == 0)
            terminal = true;
        else {
            int next = toNumber(*key);
            //해당 자식 노드가 없다면 생성한다.
            if (children[next] == NULL)
                children[next] = new TrieNode();
            //해당 자식 노드로 재귀 호출
            children[next]->insert(key + 1, id);
        }
    }
 
    TrieNode* find(const char* key) {
        if (*key == 0) return this;
        int next = toNumber(*key);
        if (children[next] == NULL) return NULL;
        return children[next]->find(key + 1);
    }
 
};

위에서부터 차례대로 살펴보자면

 

1. 문자열에서 출현할 수 있는 문자의 개수 ALPHABET (문자열에 대문자만 있다고 가정)

 

2. 주어진 문자를 0~25 범위로 변환해주는 toNumber 함수를 미리 선언한다.

 

이후 트라이의 한 노드를 나타내는 객체 TrieNode 에서 

 

3. 이 객체에서 갈 수 있는 노드 TrieNode* children[ALPHABETS]을 선언하였고,

 

4. 종료 노드를 표현하기 위한 변수 terminal 과

 

5. 이 객체를 루트로 하는 트라이에 가장 먼저 추가된 단어의 번호 first 변수를 선언해주었다.

 

terminal은 주어진 문자열이 트라이에 포함되어있는지 바로 알 수 있게 하고

(이후 등장하는 find 함수에서)

 

first는 트라이를 사용하여 만든 검색 엔진의 자동완성을 위해 필요하다.

first를 보고, 이 노드에 왔을 때 종료 노드까지 한 번에 갈 수 있는가? 를 판단할 수 있기 때문이다.

(이 코드에서 자동완성은 구현하지 않았습니다!)

 

6. 이후 생성자와 소멸자가 있으며, first는 -1로, children 객체들은 모두 0으로 초기화한다.

 

7. insert 함수는 문자열을 트라이에 넣어 위의 그림처럼 트리를 만들어 주는 아주 중요한 함수이다.

 

먼저 인자로 문자열의 포인터와 이 문자열을 기록할 id를 받는다. (id는 main함수에서 지정해주어야 합니다!)

 

만약 문자열이 끝나는 종료 부분(가리키는 포인터가 0(null 포인터)) 라면 이때 종료 노드를 표시하는

terminal 변수를 true로 바꿔주고

 

만약 종료 노드가 아니라면, 다음으로 넘어가(해당 노드의 자식 노드) insert 함수를 재귀 호출한다.

이때 children [next]->insert(key+1, id) 부분이 매우 중요한데,

이렇게 하면 연결 리스트처럼 이어져 트라이의 모양을 형성하게 된다.

 

8. 마지막으로 find 함수는 인자로 문자열이 들어왔을 때 트라이에 이 문자열이 존재하는가? 에 대한 함수이다.

 

만약 위 트라이 그림에서 "people"을 find 하려 할 때 문자열의 맨 앞을 가리키는 포인터부터 시작해

"peo"까지 재귀 호출을 하고, 이제 p를 찾으려는데 트라이의 'o' 노드에서 가리키는 노드가 더 이상 없기 대문에

NULL을 리턴하게 된다.(못 찾았다는 의미로)

 

 

 

3. 관련 문제

백준 5052번 전화번호 목록 - https://www.acmicpc.net/problem/5052

백준 9202번 Boggle - https://www.acmicpc.net/problem/9202