트라이

트라이 (Trie)

문자열의 집합을 표현하는 트리 자료구조이다. 문자열 집합 내에서 원하는 원소를 찾을 때, 문자열을 키로 사용하는 이진 탐색 트리에서는 이진 탐색(logN)과 문자열(M) 비교를 거쳐 O(MlogN) 의 시간이 걸리는 반면 트라이는 O(M) 시간만에 찾을 수 있다.

집합의 구현

#include <bits/stdc++.h>
using namespace std;

const int ALPHABETS = 26;
int toNumber(char ch){ return ch-'a'; }

struct TrieNode{
    TrieNode* children[ALPHABETS];
    bool terminal;
    TrieNode() : terminal(false){
        memset(children, 0, sizeof(children));
    }
    ~TrieNode(){
        for(int i = 0; i < ALPHABETS; i++)
            if(children[i])
                delete children[i];
    }
    void insert(const char* key){
        if(*key == 0) terminal = true;
        else{
            int next = toNumber(*key);
            if(children[next] == NULL)
                children[next] = new TrieNode();
            children[next]->insert(key+1);
        }
    }
    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);
    }
};

int main(){
    TrieNode* root = new TrieNode();
    root->insert("be");
    root->insert("bet");
    root->insert("bus");
    root->insert("tea");
    root->insert("ten");
    TrieNode* key = root->find("b");
    if(key == NULL) cout << "false\n";
    else
        if(key->terminal == true) cout << "true\n";
        else cout << "prefix\n";
    // output : prefix
    return 0;
}

트라이의 각 개체는 출현할 수 있는 문자의 개수 크기의 트라이 포인터 배열(children)과, 문자열의 끝임을 나타내는 변수(terminal)로 구성이 되어 있다.

원소를 삽입하는 insert 함수의 구현은 삽입할 문자열을 문자 하나하나씩 차례로 확인하면서 처음 등장하는 문자일 경우 트라이 객체를 새로 생성하고, 기존에 생성된 객체가 있다면(접두사가 동일한 다른 문자열이 삽입 되었다면) 재사용하여 문자열을 저장한다. 삽입할 문자열이 끝에 다다랐을 때(NULL or \0 문자일 때)는 현재 트라이 객체의 terminal 값을 true 로 변경하여 해당되는 문자가 집합에 저장되어 있음을 표시한다.

find 함수는 insert 함수와 마찬가지로 주어진 문자열을 문자 하나하나씩 차례로 트라이에 존재하는지를 살피는데 트라이 객체가 존재하지 않을 경우 NULL 를 반환하고, 존재 할 경우는 끝까지 탐색한 후 트라이 객체를 반환한다. 반환된 객체의 terminal 값에 따라 true 이면 일치하는 문자열이 있는 경우, false 이면 접두사만 일치하는 경우 로 구분할 수 있다.