TRIE

TRIE란 TREE를 응용한 문자열 알고리즘이다.

Wiki에서는 hash map을 대신할 수 있다고 되어 있는데 실제로 그렇다.

단순하게 이진트리가 아니라, 문자열을 순차적으로 순회하며 tree를 구성해주게 되는데, trie를 사용하는 장점 중 하나는 저장과 동시에 정렬이 된다는 점이다.

삼성전자 상시 역량테스트를 준비하면서 hash를 공부하는 사람들이 많은데, 사실 데이터양이 많아질수록 직접 구현한 hash일수록 index충돌이 많이 일어나서 생각보다 AutoK를 하는 경우가 생길것이다.

물론 hash에 충돌이 안나게하는 여러가지 기법이 있지만.... key값이 그리 길지 않다면 trie를 hash처럼 사용하는 것을 선호하는 편이다.

위의 그림(Wiki 참조)과 같이 문자를 하나의 key값으로 삼으며 다음 노드를 찾아서 tree를 구성하는 방식이다.

기본적으로 문자를 사용한다고는 하지만, key값을 어떻게 주고, 짜는사람이 입맛에 맞게 잘 handling만 한다면 충분히 hash map을 대체할 수 있는 유용한 알고리즘이다

먼저 trie를 구현하는 방법에는 크게 두가지가 있다.

먼저 기본적인 동적할당을 통해 trie를 구현하는 것이 있다.

동적할당은 next node가 nullptr일경우에 새로이 동적할당을 한 후, 그 포인터를 붙여주며 trie를 구성하게 된다.

정적할당은 node의 최대 갯수만큼 배열로 미리 할당한 후, next에 할당이필요한 경우에 index를 하나씩 늘려서 init해주고, 그 위치의 포인터를 root 의 next에 할당해준다.

위의 두개의 설명을 그림으로 그리고 싶으나 귀찮........

Code Wins Arguments라 했으니 코드를 올려서 찬찬히 디버깅해보시면 좋을 것 같다

동적할당만 할 줄 알았지만, C형 샘플문제인 블록 부품 맞추기 문제를 풀면서 정적할당을 처음 공부해보았다.

새벽에 잠들기전에 잠깐 보고 유레카를 외치며 잠들었다....... 생각해낸사람 갓.... 나는 똥멍청....

아래의 코드는 두가지 방법으로 각각의 class로 구현한 코드이다

항상 말하지만 내 코드는 reference이고, 입맛에 맞게, 더 효율적으로 짜면 된다

#include <iostream>
#include <malloc.h>
#define MAXSIZE 10000
using namespace std;
 
typedef struct NODE {
    char data;
    bool end;
    NODE*next[26];
    NODE() {
        Init();
    }
    void Init() {
        data = 0;
        end = false;
        for (int i = 0; i < 26; i++) {
            next[i] = nullptr;
        }
    }
}node;
 
class TRIE_STATIC {
private:
    node nodes[MAXSIZE];
    int node_idx;
 
public:
 
    TRIE_STATIC() {
        Init();
    }
    void Init() {
        node_idx = 0;
        nodes[node_idx].Init();
        node_idx++;
    }
 
    node* alloc() {
        nodes[node_idx].Init();
        node*tmp = &nodes[node_idx];
        node_idx++;
        return tmp;
    }
 
    void insert(char *buff) {
        node*tmp = &nodes[0];
        char c;
        while (c = *buff++) {
            if (tmp->next[c - 'a'] == nullptr) {
                tmp->next[c - 'a'] = alloc();
            }
            tmp->data = c;
            tmp = tmp->next[c - 'a'];
        }
        tmp->end = true;
    }
 
    bool find(char *buff) {
        node*tmp = &nodes[0];
        char c;
        while (c = *buff++) {
            if (tmp->next[c - 'a'] == nullptr) {
                return false;
            }
            tmp = tmp->next[c - 'a'];
        }
        if (tmp->end != true) {
            return false;
        }
        return true;
    }
 
};
 
class TRIE_DYNAMIC {
private:
    node *root;
public:
 
    TRIE_DYNAMIC() {
        root = alloc();
    }
 
    ~TRIE_DYNAMIC() {
        Delete(root);
    }
 
    void Init() {
        for (int i = 0; i < 26; i++) {
            if (root->next[i] != nullptr) {
                Delete(root->next[i]);
            }
        }
        root->data = 0;
        root->end = false;
    }
    void Delete(node *root) {
        node *tmp = root;
        for (int i = 0; i < 26; i++) {
            if (tmp->next[i] != nullptr) {
                Delete(tmp->next[i]);
            }
        }
        free(tmp);
    }
 
    node* alloc() {
        node* tmp = (node*)malloc(sizeof(node));
        tmp->Init();
        return tmp;
    }
 
    void insert(char *buff) {
        node*tmp = root;
        char c;
        while (c = *buff++) {
            if (tmp->next[c - 'a'] == nullptr) {
                tmp->next[c - 'a'] = alloc();
            }
            tmp->data = c;
            tmp = tmp->next[c - 'a'];
        }
        tmp->end = true;
    }
 
    bool find(char *buff) {
        node*tmp = root;
        char c;
        while (c = *buff++) {
            if (tmp->next[c - 'a'] == nullptr) {
                return false;
            }
            tmp = tmp->next[c - 'a'];
        }
        if (tmp->end != true) {
            return false;
        }
        return true;
    }
};
 
TRIE_STATIC trie_static;
TRIE_DYNAMIC trie_dynamic;
 
int main(void) {
 
    char test[4][10] = { "one", "two", "three", "test" };
 
    
 
    for (int i = 0; i < 3; i++) {
        trie_static.insert(test[i]);
        trie_dynamic.insert(test[i]);
    }
    
    for (int i = 0; i < 4; i++) {
        cout << "STATIC TRIE Result : " <<  trie_static.find(test[i]) << endl;
        cout << "DYNAMIC TRIE Result : " << trie_dynamic.find(test[i]) << endl;
    }
 
    return 0;
}