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

트라이의 정의를 위키백과의 내용을 인용하면 다음과 같습니다.

트라이(trie)는 컴퓨터 과학에서 탐색트리의 일종이다.
노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다.

 

트라이(trie) 란?

문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸릴 수 있습니다.

N개의 원소를 갖는 이진검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교만으로 찾을 수 있습니다.

이러한 이진 검색 트리에서 착안을 하여 고안된 문자열 특화 자료구조가 바로 트라이(trie) 로 집합 내에서 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다.

그렇다면 어떻게 가능한지 다음을 살펴 보시죠~

출처:위키백과

그림은 문자열집합 S={"A","to","tea","ted","ten","inn"} 을 저장하는 트라이 예를 보여 줍니다.

그림에서 볼 수 있듯이 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들의 서로 연결된 트리입니다.

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

두 노드를 연결하는 간선은 덧붙인 글자에 대응 됩니다.

만약 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 26개짜리 포인트 배열을 가지고 있습니다.

class TrieNode{
    TrieNode* children[26]; ///트라이 노드가 'A'~'Z' 까지 26개 
};

이러한 노드에 "TO" 라는 문자열을 입력하는 경우를 살펴 보면 먼저 'T' 라는 문자열의 위치에 자식노드가 있다면 해당 자식 노드에 'O' 라는 문자열을 추가 하고 없다면 'T'라는 문자열의 위치에 자식노드를 생성해서 해당 자식 노드의 위치에 "O" 라는 문자열을 추가 해 주면 됩니다.

 입력하는 코드

class TrieNode{
private: 
    bool terminal; ///마지막 문자이면 true, 중간 문자이면 false
    TrieNode* children[26]; ///트라이 노드가 'A'~'Z' 까지 26개

public:
    TrieNode(){ ///생성자
        terminal=false;
        memset(children,0,sizeof(children)); ///자식 노드를 초기화
    }
    ~TrieNode(){ ///소멸자
        for(int i=0;i<26;i++) {
            if(children[i]){
                delete children[i]; ///자식이 있으면 삭제 하자
            }
        }
    }

    void insert(const char *str){
        if(*str==0) terminal=true;
        else {
            if(children[*str - 'A']==NULL){
                children[*str - 'A'] = new TrieNode();
            }
            children[*str - 'A']->insert(str + 1); ///현재 위치 다음을 보내자
        }
    }
};

terminal을 가지고 종료노드인지 아닌지를 판단합니다.

만약 "TED"를 트라이 자료구조에 넣었다면 'T'->'E'->'D' 와 같이 자료구조가 생성이 되어 있을 것이고 'D' 위치에먼 terminal 이 true 이므로 해당 자료구조에 "TE" 가 있는지 찾을때 terminal 을 가지고 False 를 리턴 할 수 있습니다.

자료구조에 해당 문자열이 있는지 검색하는 코드는 다음과 같습니다.

class TrieNode{
private:
    bool terminal; ///마지막 문자이면 true, 중간 문자이면 false
    TrieNode* children[26]; ///트라이 노드가 'A'~'Z' 까지 26개

public:
    TrieNode(){ ///생성자
        terminal=false;
        memset(children,0,sizeof(children)); ///자식 노드를 초기화
    }
    ~TrieNode(){ ///소멸자
        for(int i=0;i<26;i++) {
            if(children[i]){
                delete children[i]; ///자식이 있으면 삭제 하자
            }
        }
    }

    void insert(const char *str){
        if(*str==0) terminal=true;
        else {
            if(children[*str - 'A']==NULL){
                children[*str - 'A'] = new TrieNode();
            }
            children[*str - 'A']->insert(str + 1); ///현재 위치 다음을 보내자
        }
    }
    
    ///찾는 부분 
    bool find(const char *str){
        if(*str==0){
            return terminal;
        }
        if(children[*str -'A']==NULL) return false;
        return children[*str -'A'].find(str+1);
    }
};

 

트라이(TRIE) 의 사용목적

• 검색어 자동완성과 같은 경우 사전에 단어를 미리 만들어 놓고 해당글자로 시작하는 단어를 표시해 줄 수 있다.
• 문자열 검사 같은 경우 사전에 단어를 미리 만들어 놓고 해당문자열이 사전에 있는지 빠르게 판단 할 수 있다.

 

 

트라이 알고리즘 사용예

백준 5670 휴대폰 자판(https://www.acmicpc.net/problem/5670)

5670번: 휴대폰 자판

이 문제는 트라이 구조로 만든 후에 자식의 수가 2개 이상 되는 경우 자판횟수를 증가 하고, 혹은 처음 시작 하는 위치에서 자판횟수를 증가 하고 다른 문자열의 끝을 지나는 경우에 자판횟수를 증가하는 형식으로 프로그래밍을 하면 된다.

 

코드예)

#include <bits/stdc++.h>

using namespace std;

class TrieNode{
private:
    bool terminal; ///마지막 문자이면 true, 중간 문자이면 false
    TrieNode* children[26]; ///트라이 노드가 'a'~'z' 까지 26개
    int childCnt; ///자식의 갯수 1개일 때는 자판을 누를 필요가 없다.
    bool isRoot;

public:
    TrieNode(bool isFirst){ ///생성자
        terminal=false;
        memset(children,0,sizeof(children)); ///자식 노드를 초기화
        isRoot = isFirst;
        childCnt=0;
    }
    ~TrieNode(){ ///소멸자
        for(int i=0;i<26;i++) {
            if(children[i]){
                delete children[i]; ///자식이 있으면 삭제 하자
            }
        }
    }

    void insert(const char *str){
        if(*str==0) terminal=true;
        else {
            if(children[*str - 'a']==NULL){
                children[*str - 'a'] = new TrieNode(false); ///처음이 아니면 무조건 false이다.
                childCnt++; ///자식을 하나 생성하자
            }
            children[*str - 'a']->insert(str + 1); ///현재 위치 다음을 보내자
        }
    }

    ///찾는 부분
    int find(const char *str){
        if(*str==0){
            return 0;
        }
        int result =0;
        if(isRoot) result++; ///처음은 무조건 1번은 키보드 눌러야 한다.
        else{
            if(childCnt>1)result++;
            else if(terminal)result++; ///hell,hello 인 경우 hell 의 teminal = true 이고 childCnt==1 이지만 hello 에서 한번 더 쳐야 함
        }
        return result + children[*str - 'a']->find(str+1);

    }
};

int main()
{

    int n;
    while(scanf("%d",&n)>0){
        vector <string> dict;
        string str;
        TrieNode node = new TrieNode(true);
        for(int i=0;i<n;i++){
            cin >> str;
            dict.push_back(str);
            node.insert(str.c_str());
        }
        int ans = 0;
        for(auto imsi : dict){
            ans += node.find(imsi.c_str());
        }

        printf("%.2f\n",(double)ans/n);
    }
    return 0;
}