문자열알고리즘-트라이(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);
    }
};

 

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

5670번: 휴대폰 자판

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

https://thinkmath2020.tistory.com/3233