Trie(트라이) 알고리즘

문자열 저장 Trie(트라이) 알고리즘 C++

Trie 알고리즘은 문자열을 저장하고, 해당 문자열의 저장 유무를 확인할 때 쓰는 알고리즘입니다.

예시

"vivid" 라는 문자열을 저장한다고 가정합시다.

가장 맨 위에 자료를 저장할 루트 노드가 있을 것이고, 그 루트 노드 아래 v를 저장,

v가 저장되어 있는 노드 아래 i가 저장

i가 저장되어 있는 노드 아래 v를 저장.. 이런 식으로 마지막 d까지 저장합니다.

 

 

여기서 가장 마지막 문자열인 vivid의 d 뒤엔 문자열의 끝을 알리는 '\0'이 붙어있을 것이므로, 이를 d 노드에 표시(노란색 노드)를 해줍시다.

이런 식으로 루트 노드 아래 저장할 단어들의 노드를 확장 시킵니다.

"vivid" 외에 "sw", "swan", "sweet"를 추가해보면 아래와 같습니다.

 

시간, 공간 복잡도

트라이는 각 문자마다 인덱싱을 해서 자료를 추가하거나 탐색하기 때문에, 찾는 문자열의 문자 수가 N 개라면 N 번만에 특정 문자열의 유무를 확인할 수 있습니다.

하지만, 인덱싱을 하면서 문자를 삽입하기 때문에, 최악의 경우에 가능한 문자 수가 M 개라고 한다면 N 개까지의 제한이 있는 문자열에선 최악의 경우 M^N의 공간 복잡도가 필요하기 때문에, 다른 알고리즘들 보다 많은 공간 복잡도를 요구합니다.

 

구현

CPP에선 Trie를 보통 구조체의 포인터 배열로 구현합니다.

구조체에 다음 인덱싱 노드의 포인터 배열들을 모두 nullptr로 선언한 뒤, 해당 공간이 필요할 때 새로운 구조체를 만들어 줍니다.

각 노드에는 필요한 값들을 저장해 준다. 예를 들어, 위 그림의 다음 문자가 '\0'인 경우도 bool형으로 체크해 주고 이용합니다.

다 쓴 Trie는 동적 할당 해제를 해주어야 합니다.

Trie의 대표 문제를 살펴봅시다.


문제 : BOJ_5052번 전화번호 목록

문제를 차근차근 읽어보면, 일관성을 판별하기 위해선 결국 다음 문자가 '\0' 인 경우로 체크되었는데, 다른 문자도 자식 노드로 갖고 있으면 일관성에 어긋나게 됩니다.

전체 소스입니다.

#include <iostream>
#include <cstring>
using namespace std;
bool isConsistent = true;
struct Trie {
    bool isWord;
    bool existChild;
    Trie* childTrie[10];
    Trie() {
        isWord = false;
        existChild = false;
        for (int i = 0; i < 10; i++) childTrie[i] = nullptr;
    }
    ~Trie() {
        for (int i = 0; i < 10; i++) {
            if (childTrie[i]) delete childTrie[i];
        }
    }

    void insert(char* word) {
        if (*word == '\0') isWord = true;
        else {
            int next = *word - '0';
            if (!childTrie[next]) childTrie[next] = new Trie;
            existChild = true;
            childTrie[next]->insert(word + 1);
        }
        if (isWord && existChild) isConsistent = false;
    }
};
int main(void) {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        isConsistent = true;
        Trie* trie = new Trie;
        int N;
        cin >> N;
        for (int j = 0; j < N; j++) {
            char word[11];
            cin >> word;
            trie->insert(word);
        }
        if (isConsistent) cout << "YES\n";
        else cout << "NO\n";
        delete trie;
    }
}

차근차근 소스를 확인해보면,

struct Trie {
    bool isWord;
    bool existChild;
    Trie* childTrie[10];
    Trie() {
        isWord = false;
        existChild = false;
        for (int i = 0; i < 10; i++) childTrie[i] = nullptr;
    }
    ~Trie() {
        for (int i = 0; i < 10; i++) {
            if (childTrie[i]) delete childTrie[i];
        }
    }
}

끝나는 문자열인가의 유무인 isWord, 자식 노드를 저장했는지 유무인 existChild, 자식 노드의 포인터 배열을 갖고 있습니다.

생성할 때 for (int i = 0; i < 10; i++) childTrie[i] = nullptr; 로 포인터 배열을 모두 null로 세팅합니다.

    void insert(char* word) {
        if (*word == '\0') isWord = true;
        else {
            int next = *word - '0';
            if (!childTrie[next]) childTrie[next] = new Trie;
            existChild = true;
            childTrie[next]->insert(word + 1);
        }
        if (isWord && existChild) isConsistent = false;
    }

삽입하는 과정입니다. 삽입해야 하는 문자열이 '\0'이라면, isWord를 true로 해주고 종료,

'\0'이 아니라면 인덱싱에 맞게 다음 문자를 삽입해 줍니다.

이때 인덱싱에 맞는 포인터 배열이 null이라면 Trie 노드를 생성해 주고, 자식 노드의 유무인 existChild도 true로 체크합니다.


마지막 줄의 if (isWord && existChild) isConsistent = false;는 일관성을 판단하는 부분입니다.

자바로도 Trie를 짤 수 있습니다.

자바는 포인터 배열이 필요 없이 new로 힙 영역에 인스턴스를 만들 수 있고, 가비지 컬렉터가 동적 할당 해제를 해준다는 장점이 있습니다.

아래는 똑같은 논리로 위의 문제를 자바로 풀이한 것입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Java_5052_전화번호목록 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++) {
            int n = Integer.parseInt(br.readLine());
            Trie trie = new Trie();
            for(int j=0;j<n;j++) {
                String word = br.readLine();
                trie.insert(word);
            }
            if(Trie.isConsistency) System.out.println("YES");
            else System.out.println("NO");
            Trie.isConsistency=true;
        }
    }

}

class Trie {
    static boolean isConsistency=true;
    // 정적 변수
    boolean isWord = false;
    boolean existChild = false;
    // 디폴트 속성
    Trie[] childTrie = new Trie[10];
    void insert(String word) {
        int len = word.length();
        Trie nowTrie = this;
        for(int i=0;i<len;i++) {
            int nextNum = word.charAt(i)-'0';
            if(nowTrie.childTrie[nextNum]==null) nowTrie.childTrie[nextNum] = new Trie();
            nowTrie = nowTrie.childTrie[nextNum];
            // 자식 그래프로 이동
            if(i==len-1) nowTrie.isWord=true;
            else nowTrie.existChild=true;
            if(nowTrie.isWord && nowTrie.existChild) isConsistency = false;
        }
    }
}