[C++] Trie (트라이) 개념과 구현방법

CS/자료구조 & 알고리즘

[C++] Trie (트라이) 개념과 구현방법

ShovelingLife 2023. 11. 28. 13:44

트라이는 "문자열을 빠르게 탐색하게 해주는 자료구조" 이다. 즉, '문자열'을 관리하는 방법 중의 하나다

작동 원리

트라이는 주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가면서 만들어 진다.

이 과정에서 반복된 재귀 호출이 이루어지는데, 말로는 무슨 말인지 모르겠으니, 이 과정을 구체적으로 알아보자.

먼저, 문자열을 트라이로 생성하는 과정부터 알아보자. 간단하게 순서를 붙여보자면 다음과 같이 진행된다.

( 지금부터 '루트(Root)' 라는 말이 나올 수 있는데, 이는 가장 초기 노드라 생각하면 된다.

즉, 연결되어 있는 어떠한 노드도 없는 초기 노드이다. )

1. 주어진 문자열에서 현재 문자를 가져온다.
2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 
노드가 없다면 그 노드를  새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.
3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다.

위의 과정을 그림으로 한번 알아보자.

문자열, [ ABC , ABCD , BCG , ZYX ,BDE ] 를 순차적으로 삽입하는 과정을 알아보자.

가장 초기, 루트노드에는 아무런 값도, 노드도 존재하지 않는다. 즉, 다음과 같은 상태일 것이다.

그럼, "ABC" 부터 트라이에 삽입해보자.

1. 주어진 문자열에서 현재 문자를 가져온다.

지금 주어진 문자열 'ABC'에서 아직 아무런 문자도 삽입하지 않았으므로, 현재 문자는 가장 앞에 있는 문자인 'A'를 가르키고 있을 것이다.

2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를 새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

그렇다면, 현재 노드는 'Root'노드이다. 그런데, 이제 문자 'A'를 삽입을 해야 하는 상황인데, 루트 노드에는 아직 아무런 노드도 생성되지 않았다. 즉 ! 'A'를 가르키고 있는 노드도 생성되지 않았으므로 생성을 해준다.

그 후, "해당노드를 통해 다음 문자열을 탐색" 이라고 했다. 즉, 이제는 현재 노드가 루트노드가 아니라, 저 'A'라는 노드가 될 것이다. 그 다음 문자열은 'BC'가 될 것이다.

또 한번 진행해보자. 현재 문자는 'B'가 될 것이다. 그런데 A → B로 가는 노드가 존재하지 않으므로 생성해준다.

그 이후, 'B'라는 노드를 통해 그 다음 문자열을 탐색해보자.

현재 노드는 'B'이고, 그 다음 문자는 이제 'C'가 될 것이다. B → C 역시 없으므로 노드를 생성해주자.

이제 'C'라는 노드를 통해 그 다음 문자열을 탐색해보자.

그런데, 그 다음 문자열을 탐색하려고 보니 문자열이 이제 끝나서 더 이상 존재하지 않으므로 삽입이 끝난 것이다.

끝난 문자열이라는 것을 표시해주기 위해서 C옆에 ★을 붙여놓겠다.

그 다음 "ABCD"를 삽입해보자.

지금 현재 노드는 가장 초기 노드인 루트노드일 것이다. 가장 먼저, 첫 번째 문자인 'A'를 탐색해보자.

그런데 이미, "ABC"를 삽입할 때 만들어 놓은 'A'로 가는 노드가 존재한다. 그렇다면 이 경우에는 노드를 새로 생성하지 않고

해당 노드를 통해서 다음 문자를 탐색한다.

그럼, 더 이상의 추가된 노드 없이 'B'로 넘어가보자. 그런데 현재노드 'A'에서 'B'로 가는 노드도, "ABC"를 만들 때 만들어 놓은 노드가 존재한다. 그렇다면 또 추가적인 노드 할당 없이 그 다음 노드로 넘어가보자.

'C'도 똑같이 존재한다. 또 노드 할당 없이 그 다음 노드로 넘어가보자.

그 다음 노드는 'D'이고, 현재 노드는 'C'이다. 이번에는 C 에서 D로 넘어가는 노드가 생성되어 있지 않다.

왜냐하면, "ABC" 문자열은 'C'에서 끝나버렸기 때문이다. 그렇다면 노드를 생성해주고, 'D'로 넘어간 후에, 끝났다는

표시까지 한번에 해주자. 그럼 다음과 같이 상태가 존재할 것이다.

그 다음 "BCG" 라는 문자열을 삽입해보자.

새로운 문자열을 삽입하기 때문에 다시 현재 노드는 루트노드로 돌아오게 된다.

그럼 가장 첫번째 문자인 'B'문자 부터 확인해보자.

루트노드에서 'B' 문자로 가는 노드가 생성되어 있지 않다. 현재 루트노드에서 생성된 노드는 'A'로 가는 노드 뿐이다.

따라서, 'B'노드를 생성해주자.

그렇다면 위와 같이 생성될 것이다.

그 다음 문자인 'C'로 넘어가보자. 'B'에서 'C'로 가는 노드가 존재하지 않는다.

왜 ??? 루트 → A → B → C 로 가는 루트에, B → C로 가는 노드가 존재하는게 아닐까??

아니다. 루트 → A → B → C로 가는데 존재하는 'B → C' 는 루트에서 A를 통해서 B로 가고, B를 통해서 C로 가는

경우이다. 우리가 지금 하고자 하는 것은, 루트 → B → C 로 가는 경우이다. 즉, 존재하지 않으므 생성해주자.

그 이후, 'C' 노드에서 'G' 노드로 연결된 노드가 없으므로, 생성해주고 끝났다고 표시를 해주자.

이 후, 순차적으로 'ZYX', 'BDE'를 넣어보는 과정을 하게되면, 글이 너무 길어지는 관계로 결과만 알아보자.

위의 원리와 똑같이 삽입해주면 다음과 같이 트라이가 구성될 것이다.

이게 트라이에 문자열을 삽입하는 과정이고, 모두 삽입한다면 위와 같은 형태를 띄게 된다.

그렇다면, 이제 잘 들어가졌는지 확인을 한번 해보자.

우리는 "ABC"라는 문자가 잘 들어가 졌는지 확인을 해보고 싶다. 그럼 삽입할 때와 똑같이 "ABC"를 탐색해보자.

가장 먼저 첫 번째 문자인 'A'가 루트노드에서 갈 수 있는지 체크해보자.

루트노드에서 'A'로 가는 노드가 존재하므로, 그 다음 문자로 넘어가보자.

'A'노드에서 그 다음 문자인 'B' 노드로 갈 수 있으므로 또 넘어가보자.

'B'노드에서 그 다음 문자인 'C'노드로 갈 수 있으므로 또 넘어가보자.

우리가 찾고자 하는 문자열은 "ABC"이다. 즉, 이제 문자열이 끝난 상황이다. 그런데 마침 'C'에 ★가 쳐져있다.

즉, 문자열이 끝났다는 표시가 되어있다. 그렇다면, "ABC"는 존재하는 문자열이라는 것을 확인할 수 있다.

한번만 더 확인해보자. 이번에는 "BTA" 라는 문자열을 찾아보자.

가장 첫 번재 문자인 'B'가 루트노드에서 갈 수 있는지 체크해보자.

생성된 노드가 있으므로, 'B'노드로 넘어가보자.

'B'노드에서 'T'로 갈 수 있는 노드가 있는지 봤더니, B에서는 'C'와 'D'밖에 존재하지 않는다.

즉, 'T'는 존재하지 않는다. 만약, "BTA"가 정확하게 생성된 문자열이였다면, 당연히 B에서 T로 가는 노드 또한

존재했을 것이다. 그런데 해당 노드가 존재하지 않는다는 말은 ? 트라이에 삽입되지 않은 문자열이라는 것을 의미한다.

즉, "BTA"는 존재하지 않는 문자열 이라는 것을 알 수 있다.

이런식으로 문자열을 찾는데 사용되는 자료구조이다.

구현

struct Trie {
    bool finish; // 끝나는 지점을 표시해줌
    Trie* next[26]; // 26가지 알파벳에 대한 트라이

    // 생성자
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }

    // 소멸자
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }

    // 트라이에 문자열 삽입
    void insert(const char* key) {
        if (*key == '\0')
            finish = true; // 문자열이 끝나는 지점일 경우 표시
        else {
            int curr = *key - 'A';
            if (next[curr] == NULL)
                next[curr] = new Trie(); // 탐색이 처음되는 지점일 경우 동적할당
            next[curr]->insert(key + 1); // 다음 문자 삽입
        }
    }

    // 트라이에서 문자열 찾기
    Trie* find(const char* key) {
        if (*key == '\0') return this; // 문자열이 끝나는 위치를 반환
        int curr = *key - 'A';
        if (next[curr] == NULL) return NULL; // 찾는 값이 존재하지 않음
        return next[curr]->find(key + 1); // 다음 문자를 탐색
    }
};

시간 및 공간 복잡도

문자열의 최대 길이가 n일 때, Find와 Insert 모두 문자열의 길이(트리의 최대 높이) 내로 끝나기 때문에 O(n)의 시간 복잡도를 가지는 것을 알 수 있다.

위의 시간 복잡도 O(n)을 가지기 위해서는 다음 문자를 가리키는 노드가 필요하다. 예를 들어, 숫자에 대해 트라이를 만들어야 한다면 0~9, 총 10개의 포인터 배열이 있어야하며, 알파벳 소문자에 대해 트라이를 만든다면 a~z인 총 26개의 포인터 배열을 가지고 있어야 한다.

즉, 최종 메모리는 O(포인터의 크기 * 포인터 배열의 개수 * 트라이에 존재하는 총 노드의 개수)가 된다.

Radix tree (Compact prefix tree)

트라이의 치명적인 단점인 공간에 대한 효율성을 최적화하기 위한 방법 중 하나이다. 아래 그림처럼 자식 노드가 하나밖에 없는 경우, 부모 노드에 모두 합치는 방식으로 필요한 메모리를 줄일 수 있다. 이 글에서는 따로 구현하는 방식은 설명하지 않는다.