[ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++)

이번 글에서는 자료구조 트라이(TRIE) 에 대해서 알아보자.

1. 트라이 (TRIE) ??

먼저 '트라이'가 무엇인지에 대해서 부터 알아보자.

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

될 것 같다.

문자열을 빠르게 탐색할 수 있다는 장점 이외에도 문자열을 관리하는데 있어서 좋은점을 많이 가진 자료구조이니

이 부분에 대해서는 트라이에 대해서 지금부터 알아본 후에 마지막으로 다시한번 정리해보도록 하자.

2. 트라이의 작동원리

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

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

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

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

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

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

2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를

  새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다.

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

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

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

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

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

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

가르키고 있을 것이다.

2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를

  새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

그렇다면, 현재 노드는 'Root'노드이다. 그런데, 이제 문자 'A'를 삽입을 해야 하는 상황이다.

그런데, 루트 노드에는 아직 아무런 노드도 생성되지 않았다. 즉 ! 'A'를 가르키고 있는 노드도 생성되지 않았다는 것이다.

그럼, 생성을 해준다.

이렇게 될 것이다. 그 후, "해당노드를 통해 다음 문자열을 탐색" 이라고 했다.

즉, 이제는 현재 노드가 루트노드가 아니라, 저 'A'라는 노드가 될 것이다. 그 다음 문자열은 'BC'가 될 것이다.

2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를

  새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

3번 과정은 어차피 2번 과정의 반복이므로, 따로 언급하지 않았다.

또 한번 진행해보자. 현재 문자는 '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"는 존재하지 않는 문자열 이라는 것을 알 수 있다.

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

3. 트라이 구현하기

그럼 지금부터는 직접 코드로 구현해보는 방법에 대해서 알아보자.

트라이를 어떻게 구현하냐에 따라 할 수 있는 정말 많은 것들이 있지만, 이번 글에서는 정말 대표적이고 간단하게

트라이에 '삽입'하는 과정과 '찾기' 과정만 다뤄보겠다.

먼저, 트라이를 생성하기 위해서 'TRIE'라는 이름으로 만든 구조체와, 그 구조체에서 사용하는 멤버변수들이다..

struct TRIE
{
    bool Finish;
    TRIE *Node[26];
    TRIE() 
    { 
        Finish = false;  
        for (int i = 0; i < 26; i++) Node[i] = NULL;
    }
}
 

line 3) 'Finish'변수는 위에 그림에서 나타낸 ★를 의미한다. 즉, 문자열이 끝난 지점에 Finish = true로 체크를 해주기 위해서
사용하는 변수이다.
line 4) TRIE *Node[26] 이 변수는 우리가 지금까지 계속해서 만들어왔던 트라이의 '노드'이다. 26칸으로 설정한 이유는
알파벳이 총 26개이기 때문이다. 알파벳이 아니라면, 이 배열의 크기도 상황에 맞게 적절하게 바꿔주면 된다.
이번 글에서는 위에서 말한 문자열들을 예시로 들고 있으므로, 26칸으로 설명을 하겠다.
line 5 ~ 9) 기본적인 생성자이다. '노드를 할당한다' 라는 말이 굉장히 많았었는데, 모두 이 생성자를 통해서 생성해줄 것이다

그럼, 삽입하는 함수를 알아보자.

void Insert(char *Str)
{
    if (*Str == NULL)
    {
        Finish = true;
        return;
    }
 
    int Cur = *Str - 'A';
    if (Node[Cur] == NULL) Node[Cur] = new TRIE();
    Node[Cur]->Insert(Str + 1);
}

위의 코드가 본인이 구현한 트라이에 'Str'이라는 문자열을 삽입하기 위한 과정이다.

라인별로 어떤 역할을 하는지 알아보자.

line 3 ~ 7) 마지막 종료 조건문 이므로 마지막에 설명 하겠다.

위의 코드를 통해서, "ABC"를 삽입하는 과정을 알아보자. 가장 처음 초기 호출한 노드는 루트노드이다.

아무런 노드도 연결되지 않은, 루트노드만 있는 상태라고 가정해보자.

line 9)

문자열에서 '현재문자'를 가져오는 과정이다. Str = "ABC" 일 때, *Str = 'A'가 된다.

이를, 위에서 선언한 멤버변수 Node[26]에 이미 존재하는지 확인하기 위해서 알파벳을 정수로 바꾼 것이다.

line 10)

현재 연결된 노드가 없는 경우이다. 이 경우에는 '노드를 생성하고 그 다음 문자열을 탐색' 하라고 했다.

따라서, 해당 노드를 생성해주는 과정이다. 만약, 기존에 다른 문자열에 의해서 노드가 이미 존재한다면, 이 조건문에는

걸리지 않을 것이다.

line 11)

해당 노드를 통해서 그 다음 문자열로 넘어가는 과정이다. Str = "ABC"라고 했을 경우, Str + 1을 하게 되면, "BC"가

호출되어진다.

다시 재귀를 타고 들어오게 되면, Str = "BC"인 상태로 들어올 것이다. 현재 노드는 "A"이다.

line 10)

'A' 에서 'B'로 가는 노드가 존재하는지 확인하고, 없으므로 노드를 생성해준다.

line 11)

'B'노드를 통해서 'C'로 재귀호출 !

line 10)

'C'노드가 없으므로 노드를 생성해주고, 그 다음 문자열로 넘어간다.

그런데, 그 다음 문자열은 문자열의 끝을 나타내는 '\0' 즉, null 이다. 따라서, 이 때 line 3) 에 걸리게 된다.

line 3)의 의미는 "문자열이 끝났다면" 을 의미한다. 즉, 끝났으므로 Finish = true로 설정해준다. 위에 그림에서

★ 를 표시한 것과 같은 의미이다.

위와 같은 방식으로 문자열 "ABC"가 트라이에 삽입되는 것이다.

그럼 특정 문자열을 찾아보자. 현재 트라이의 상태는, 우리가 위에서 공들여 만들어 놓은 이 상태라고 가정하자.

bool Find(char *Str)
{
    if (*Str == NULL)
    {
        if (Finish == true) return true;
        return false;
    }
    int Cur = *Str - 'A';
    if (Node[Cur] == NULL) return false;
    return Node[Cur]->Find(Str + 1);
}

이 상태에서 "ABC"라는 문자열을 찾는 과정을 알아보자. 위의 코드는 본인이 구현한 Str이라는 문자열을 찾는 부분이다.

만약, 해당 문자열을 찾았다면 true를 반환, 그게 아니라면 false를 반환하도록 만든 코드이다.

코드가 삽입하는 코드와 굉장히 비슷하다.

line 9)

노드가 생성되지 않았다면 바로 false를 반환해버리는 부분이다.

왜냐하면, 찾고자 하는 문자열이 트라이에 삽입되어 있는 문자열이라면, 삽입하는 과정에서 당연히 노드가 생성되어

있을 것이다. 그런데, 문자열을 찾는 도중에 생성되지 않는 노드가 존재한다 ? 이 말은 즉, 트라이에 없는 문자열이라는 것을

의미하기 때문이다.

line 3)

찾고자 하는 문자열의 마지막까지 탐색을 했을 경우이다. 이 경우라고 해서, 무조건 해당 문자열이 존재하는 것이 아니다.

우리가 만들어 놓은 트라이에서 "AB"라는 문자열을 찾는다고 생각해보자.

루트 → 'A'가 있으므로, 노드를 잘 타고 넘어와서, A → B도 있으므로 잘 타고 넘어올 것이다.

그 이후, line 3에 걸릴텐데, 우리가 트라이에 삽입한 문자열은 "ABC"와 "ABCD"이지, "AB"라는 문자열은 없는 문자열이다.

즉, line 3) 까지 왔다고 하더라도, 해당 문자열이 마지막 문자열인지 확인을 해줘야 한다.

따라서 line 5)와 같은 조건문을 설정해 준 것이다.

다시 본론으로 넘어와서 "ABC"를 찾는 경우, 'C'까지 간 이후에, line 3) 에 걸릴 것이다.

그런데, 'C'는 Finish가 true로 설정되어 있다. 즉, 문자열의 마지막이라는 이야기이다. 그래서 "ABC"는 존재하는 문자열

이라고 판단할 수 있는 것이다.

본인은 위와 같이 코드를 한번 구현해 보았다. 이 외에도 어떻게 구현하냐에 따라서 정말 많은 것을 할 수 있는 자료구조 이다 !!

4. 트라이의 좋은 점 ??

위에서도 말했고, 우리가 계속 해왔듯이, '문자열의 탐색'에 있어서 굉장히 유용한 자료구조이다.

또한, 어떤 함수를 어떻게 구현하는지, 어떤 멤버변수를 선언해서 어떻게 관리하는지에 따라서 문자열에 관련된

여러가지 역할을 해내기에 충분히 좋은 자료구조이다.

또 하나는, 트라이에 삽입만 하게 된다면, 자동으로 정렬된 효과를 볼 수 있다는 점도 좋은 점 중 하나라고 생각한다.

어떻게 정렬된 효과를 볼 수 있을까 ??

우리가 삽입과정을 알아본 예시를 보면 [ ABC , ABCD , BCG , ZYX ,BDE ] 이 순서대로 삽입을 했다.

그런데, 순서를 바꿔서 [ ZYX , BCG , ABC , BDE , ABCD ] 순서대로 삽입을 했다고 생각해보자.

그럼 트라이의 결과과 달라졌을까?? 아니다. 똑같이 위와 같은 형태일 것이다.

우리는 알파벳을 관리하기 위해서 '26'칸의 노드배열을 생성해 주었다. 루트노드부터, 탐색을 하는데

0번칸부터 탐색해서, 생성된 노드들만 출력을 하게 된다면 ?? 대략 코드로 짜보면 이런 상황을 말하는 것이다.

void IsSorting(TRIE *N, char Str[], int Idx)
{
    if (N->Finish == true) cout << Str << endl;
    for (int i = 0; i < 26; i++)
    {
        if (N->Node[i] != NULL)
        {
            char C = i + 'A';
            Str[Idx] = C;
            N->IsSorting(N->Node[i], Str, Idx + 1);
        }
    }
}
 
int main(void)
{
    TRIE *Root = new TRIE();
    char *String[5];
    String[0] = "ZYX";
    String[1] = "BCG";
    String[2] = "ABC";
    String[3] = "BDE";
    String[4] = "ABCD";
 
    for (int i = 0; i < 5; i++)
    {
        Root->Insert(String[i]);
    }
 
    for (int i = 0; i < 26; i++)
    {
        if (Root->Node[i] != NULL)
        {
            char Str[5] = { NULL };
            Str[0] = i + 'A';
            Root->IsSorting(Root->Node[i], Str, 1);
        }
    }
}

이런식으로, Insert하는 순서를 보면, 정렬된 순서가 아니지만, 삽입한 후에, line30) 으로 노드를 작은순으로 돌면서

탐색을 하게 되면, 정렬된 효과를 볼 수 있다.

실제로 출력하면 다음과 같은 출력창이 뜬다.

트라이는 이런 자료구조이다 !