Trie(트라이) 자료구조

Trie 자료구조?

Prefix Tree 라고 불리는 Trie 자료구조는 특정 문자열을 탐색하는데 최적화 된 자료구조이다.

문자열 배열에서 특정 문자열 ${S_i}$를 탐색하는데 걸리는 시간은 ${O(length(S_i))}$ 가 된다.

이러한 시간복잡도는 문자열 배열에서 정확하게 특정 문자열만 탐색하여야 가능한 시간복잡도이다.

어떤 방식으로 이렇게 시간복잡도를 최적화 하였을까?

 

Trie 는 트리형 자료 구조를 기반으로 하는 탐색에 특화 된 자료구조이다.

보통, 탐색을 위해 트리형 자료 구조를 사용하는 경우 탐색을 위한 key와 해당 되는 키에 매핑되는 value 형태로 저장하는데

(이를, Associative array 라고 한다 https://en.wikipedia.org/wiki/Associative_array )

Trie에서는, 따로 노드들이 key값을 가지지 않고 각각의 노드들이 key를 대신한다. 즉, 각각의 노드들이 key를 정의한다.

이러한 방식을 가볍게 예시를 통해, 살펴보고 가자.

 

Trie 와 다른 Associative Array 와의 차이점

예시( balanced binary tree )

쉽게 stl 에서 dictionary 혹은 map이라고 명명된 Associative array의 일종이다.

{key, value} = {정수, 정수에 매핑되는 문자열} 이라고 가정을 하고 이것을 노드라고 부르겠다.

// Binary Search Tree 설명을 위한 Simple한 노드의 정의 
struct BSTNode{
    pair<int, string> nodeInfo;
    BSTNode* next[2]; // Binary Tree // [0] : left, [1] : right
    
};

또한, 루트 노드보다 작은 key값을 가지는 노드는 왼쪽 자식으로 루트 노드보다 큰 key값을 가지는 노드는 오른쪽 자식으로 삽입된다고 가정하자.

 

Balanced Binary Tree

 

BSTNode* find(BSTNode* current, const int targetKey){
	// target을 끝까지 찾지 못한 경우
	if( current == nullptr )
    	return nullptr;
        
    // target을 찾은 경우
	if( current -> nodeInfo.first == targetKey )
    	return current;
        
	int currentKey = current->nodeInfo.first;
    return currentKey > targetKey ? find(current->next[0], targetKey) : find(current->next[1], targetKey);
}

탐색을 위한 특정한 Key가 주어졌을 때, 균형잡힌 이진탐색트리의 루트노드에서 부터 key값을 비교하며 자식 노드로 분기한다는 방식인데

이러한 방식은 트리의 높이당 1번씩 비교연산을 하므로, 트리의 높이(h) = $O({\left\lceil log_2{N} \right\rceil})$ 만큼의 시간복잡도를 요구한다. 

 

예시2( Trie )

trie에서는 각각의 노드에서 Key를 저장하지 않는다. 대신에 각각의 노드가 차지하는 위치(?)가 Key를 대신하는 방식으로 진행된다.

이를 통하여, 매번 Key를 비교하는 방식으로 분기하는 것이 아닌 O(1)의 방식으로 원하는 위치로 즉각적으로 분기할 수 있다.

이는 N시간 만큼 비교연산을 수행하지 않는 점에서 매우 효율적이라고 할 수 있다.

struct TrieNode{
    int countEndingWithThis;
    TrieNode* child[256]; // 문자 1개 = ascii(1바이트) = 256가지의 상태 표현
    TrieNode(){countEndingWithThis = 0, memset(child, 0, sizeof(child));}
};

위와 같이 Trie의 노드를 정의해보자. ( 코드에 대한 자세한 설명은 아래에 남겨 놓을 예정이니, 느낌만 잡고 가자 )

위에서 살펴본 BSTNode와는 다르게, 탐색을 위한 key가 따로 정의되어 있지 않다.

이는, child[key]가 key를 대신하기 때문이다. 즉 TrieNode자체가 키를 대신한다. (문자열에서 효과적이다)

character 말고도 다른 타입도 적절한 Hashing 을 통하여 child[key]에 매핑할 수 있다면 Trie로 표현하는 것이 가능하지만 너무 많은 상태를 표현해야 할 수 있으므로, child배열의 size가 기하급수적으로 커질 수도 있다는 단점이 존재한다.

이것이 다른 Associative array 형태의 자료구조와 가장 구분되는 차이점이라고 할 수 있겠다.

---

Trie 자료구조 정의

Suffix Tree라는 이름으로도 불리는 Trie 자료구조는 말 그대로 "접두사를 표현하는 트리"이다.

접두사를 따라가면서 원하는 target을 찾고자 하는 것이 핵심이자 전부라고 말할 수 있다. 

이러한 특성을 살리기 위해 각각의 노드들은 접두사를 표현한다.

 

Trie또한 트리이고 트리의 특성 상, 최상위 루트 노드는 모든 노드들의 부모 노드이고 trie내의 모든 접두사들은 루트 노드의 key를 포함하므로 우리는 이것을 아무런 값도 가지지 않는 더미노드로 대체한다.( 최상위 루트 노드가 표현하는 접두사는 아무것도 없다 )

 

 

Trie ( 숫자들은 단순하게 노드를 구분하기 위해 적어 둠 ) 

위와 같은 형태를 가진 트리를 Trie라고 하고, 각각의 노드는 ( 해당 노드의 부모들이 표현한 접두사 + 자기 자신의 고유한 접두사 ) 를 표현한다.

그렇다면 1번 노드 ~ 6번 노드 까지는 다음과 같은 문자열을 표현한다고 볼 수 있다.

노드 번호	표현하는 문자열
1	"a"
2	"b"
3	"aa"
4	"ab"
5	"ac"
6	"ba"

---

Trie 구현 

트리 순회 방식에 대하여 지식이 있다면, 구현 자체는 난이도가 그다지 어렵지 않으므로 주석으로 설명을 대체하겠다. 

Trie의 노드

struct TrieNode{
    int countEndingWithThis; // 해당 노드로 끝나는 문자열의 개수
    TrieNode* child[256]; // ascii(1바이트) = 256가지의 상태 표현
    TrieNode(){countEndingWithThis = 0, memset(child, 0, sizeof(child));}
};

중복되는 문자열이 존재할 수 있으므로, 현재 노드로 끝나는 문자열의 개수를 저장하여 출력 시 개수까지 올바르게 출력한다.

 

Trie 자료구조

class Trie{
public:
    TrieNode* root;
    Trie(){ root = new TrieNode(); }
    void insert(TrieNode* current, const string& str, int idx){
        if( idx == str.size() ){
            // 모든 문자들이 할당 되었을 경우, 해당 노드에 마킹한다.
            ( current -> countEndingWithThis ) += 1;
            return;
        }
        // 만약, 새로운 접두사가 할당 되었을 경우 노드를 생성한다.
        if( current -> child[str[idx]] == nullptr )
            current -> child[str[idx]] = new TrieNode();

        // 새로 마킹할 위치 탐색 진행.
        TrieNode* next = current -> child[str[idx]];
        insert(next, str, idx+1);
    }
    TrieNode* find(TrieNode* current, const string& str, int idx){
        // 해당 문자열이 trie 내에 존재하지 않는 경우
        if( idx != str.size() && current == nullptr )
            return nullptr;
        if( idx == str.size() && current->countEndingWithThis > 0 )
            return current;
        return find(current->child[str[idx]], str, idx+1);
    }
};

 

Trie 자료구조 전체 코드 + 테스트 코드

#include <iostream>
#include <utility>

using namespace std;
struct TrieNode{
    int countEndingWithThis; // 중복되는 문자열이 있을 경우 count up
    TrieNode* child[256]{}; // ascii(1바이트) = 256가지의 상태 표현
    TrieNode(){countEndingWithThis = 0, memset(child, 0, sizeof(child));}
};
class Trie{
public:
    TrieNode* root;
    Trie(){ root = new TrieNode(); }
    void insert(TrieNode* current, const string& str, int idx){
        if( idx == str.size() ){
            // 모든 문자들이 할당 되었을 경우, 해당 노드에 마킹한다.
            ( current -> countEndingWithThis ) += 1;
            return;
        }
        // 만약, 새로운 접두사가 할당 되었을 경우 노드를 생성한다.
        if( current -> child[str[idx]] == nullptr )
            current -> child[str[idx]] = new TrieNode();

        // 새로 마킹할 위치 탐색 진행.
        TrieNode* next = current -> child[str[idx]];
        insert(next, str, idx+1);
    }
    TrieNode* find(TrieNode* current, const string& str, int idx){
        // 해당 문자열이 trie 내에 존재하지 않는 경우
        if( idx != str.size() && current == nullptr )
            return nullptr;
        if( idx == str.size() && current->countEndingWithThis > 0 )
            return current;
        return find(current->child[str[idx]], str, idx+1);
    }
    void printAllElem(TrieNode* current, string accumulatePrefix){
        if( current != nullptr && current->countEndingWithThis > 0 ){
            for(int i=0; i<current->countEndingWithThis; i++){
                cout << accumulatePrefix << '\n';
            }
        }
        for(int i=0; i<256; i++){
            if( current->child[i] == nullptr ) continue;
            char newPrefix = (char)i;
            printAllElem(current->child[i], accumulatePrefix + newPrefix);
        }
    }
};
int main(void){
    string strWithNoDup[] = {"hello","my","name", "is", "minjun", "nice", "to", "meet", "you", "my sweet heart"};
    string strWithDup[] = {"a", "aa", "aaa", "a", "aaa", "aaa"};
    Trie trie1, trie2;

    // insert test
    for(const auto& s: strWithNoDup) {
        trie1.insert(trie1.root, s, 0);
    }
    for(const auto& s: strWithDup){
        trie2.insert(trie2.root, s, 0);
    }

    // find test
    for(const auto& s : strWithNoDup){
        auto pos = trie1.find(trie1.root, s, 0);
        if( pos != nullptr )
            cout << "found\n";
        else
            cout << "not found\n";
    }
    for(const auto& s : strWithDup){
        auto pos = trie2.find(trie2.root, s, 0);
        if( pos != nullptr )
            cout << "found\n";
        else
            cout << "not found\n";
    }

    cout << "\n===========\n";

    // print all elements in trie tree
    trie1.printAllElem(trie1.root, "");
    trie2.printAllElem(trie2.root, "");

    return 0;
}

 

Trie의 시간복잡도 & 공간복잡도

탐색

탐색하고자 하는 문자열의 길이(L)만큼의 탐색 시간이 필요하게 된다. O(L)

 

추가

해당하는 prefix만큼 노드를 따라 탐색하다가 새로운 prefix가 나온다면 추가하는 방식으로 진행되기 때문에 최대 추가하고자하는 문자열의 길이(M)만큼의 시간복잡도를 갖는다. O(M)

 

공간복잡도

trie에서 제일 치명적인 부분이다. 앞에서 언급했다시피, trie는 associative array형태를 가지는 자료구조이고 이는 key <-> value의 쌍을 이용하는데, trie에서는 노드 자체를 key값으로 가지므로 들어올 수 있는 모든 경우의 prefix 를 노드로 저장해야함을 의미한다.

그렇다면, insert연산 시 이전에 중복되는 prefix가 없다면 매번 해당하는 노드를 추가하는 것이 되겠고 이 경우 trie에 들어가는 문자열들의 총 길이만큼의 노드가 생성된다. (노드의 크기는 정의하는 것에 따라 달라질 수 있다)

O( Node의 총 개수 * Node의 크기 ) => Node의 총 개수의 최악 : 모든 문자열들의 길이 합.