C/C++] 트라이(Trie) 알고리즘을 만들어보자!!

문자열을 (m log n)의 형태로 빠르게 찾는 알고리즘입니다.

 

구성은 Tree 형태로 만들어지며 입력은 다음과 같이됩니다.

 

"like, bike, bool, book"을 입력받는다고 가정한다면,

 

이런식으로 들어가게 됩니다.

 

여기서 root 노드에서 자식노드로 갈 수 있는 경우의 수는 26가지 입니다.

 

왜냐???!!!

 

영어 알파벳은 26개 이기 떄문입니다.(대문자 제외)

 

그래도 모르시겠다고요??!!

 

영어 알파벳은 a ~ z 까지 있습니다.

 

이것의 갯수는 26개 입니다.

 

그럼 영어 단어들의 첫번째 문자로 올 수 있는 경우의 수는 26가지가 되는 것입니다.

 

예를들어 apple, banana, like, etc.....

 

apple은 a로 시작하고 banana는 b로, like는 l로 시작합니다.

 

즉, 시작단어로 올 수 있는 알파벳 수는 26가지중 하나란 소리입니다.

 

트라이 구조로 문자열을 비교할 때 하나 하나 늘어날 때마다 26가지의 경우의 수를 가지고 늘어난다는 뜻입니다.

 

하지만 우리는 이것을 O(n)로 비교할 수 있습니다.

 

노드마다 알파벳 배열을 만든 후 해당 알파벳에 맞는 index로 찾아가면 되는 것입니다.

(더이상 설명하면 더 햇갈릴것 같아서 여기까지만 하겠습니다.)

 

 

 

그럼 차근차근 만들어 보겠습니다.!!

 

알파벳 갯수는 26개로 고정값입니다.

 

그리고 트리를 만들어야할 노드가 필요합니다.

#include <iostream>
#include <cstdio>
#include <string>

const int ALPABATS = 26;

class Tri_Node {
    Tri_Node * child[ALPABATS];


    Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            child[i] = NULL;
    }

    ~Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            if (child[i] != NULL)
                delete child[i];
    }
};

int main(void) {

    Tri_Node tri;

    return 0;
}

 

 

우선 int형 자료형 ALPABATS를 26으로 선언하고 Tri_Node를 담을 수 있는 포인터 변수 배열을 26 크기만큼 만듭니다.

 

생성자와 소멸를 선언해주고 child의 모든 값을 NULL로 지정해주고 있습니다.

 

 

 

그럼 insert를 만들어 보겠습니다.

 

insert는 아래와 같이 진행할 것입니다.

 

 

 

#include <iostream>
#include <cstdio>
#include <string>

const int ALPABATS = 26;

class Tri_Node {
private:
    Tri_Node * child[ALPABATS];

public:
    Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            child[i] = NULL;
    }

    ~Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            if (child[i] != NULL)
                delete child[i];
    }

    int tonum(char c) {        //문자를 숫자로 변환.
        return tolower(c) - 'a';    //대문자인 경우는 소문자로 변환.
    }

    void insert(const char * words) {
        if (*words == '\0')        //입력받은 words가 '\0'일 경우, 즉 문자열 끝인 경우.
            return;

        int next = tonum(*words);

        if (child[next] == NULL) {
            child[next] = new Tri_Node();
        }
        child[next]->insert(words + 1);
    }
};

int main(void) {

    Tri_Node tri;

    return 0;
}

여기서 child[next]->insert(words + 1);

를 해주고 있는데 words + 1은 words의 주소값을 1 증가시키는 것입니다. 즉 다음 단어를 가리키게 되는 것이죠.

 

 

 

 

 

 

그럼 이제 find() 함수를 만들어 보겠습니다.

 

find()도 insert와 동일하게 찾아주되, 다음 단어가 가르키는 곳이 NULL이라면...

 

즉, 입력이 이뤄진 것이 아니기 때문에 false를 반환해 주면 됩니다.

 

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

const int ALPABATS = 26;

class Tri_Node {
private:
    Tri_Node* child[ALPABATS];

public:
    Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            child[i] = NULL;
    }

    ~Tri_Node() {
        for (int i = 0; i < ALPABATS; i++)
            if (child[i] != NULL)
                delete child[i];
    }

    int tonum(char c) {        //문자를 숫자로 변환.
        return tolower(c) - 'a';    //대문자인 경우는 소문자로 변환.
    }

    void insert(const char* words) {
        if (*words == '\0')        //입력받은 words가 '\0'일 경우, 즉 문자열 끝인 경우.
            return;

        int next = tonum(*words);

        if (child[next] == NULL) {
            child[next] = new Tri_Node();
        }
        child[next]->insert(words + 1);
    }

    bool find(const char* words) {
        int next = tonum(*words);

        if (*words == '\0')
            return true;

        if (child[next] == NULL)
            return false;

        return child[next]->find(words + 1);
    }
};

int main(void) {

    Tri_Node tri;

    tri.insert("like");

    if (tri.find("like"))
        cout << true << endl;
    else
        cout << false << endl;
    
    if (tri.find("bike"))
        cout << true << endl;
    else
        cout << false << endl;
        

    return 0;
}

 

 

잘 되는걸 확인 할 수 있습니다.

 

 

그 이후의 응용은 여러분들 몫입니다.