Trie

  • Trie란 prefix tree라고도 불림
  • 문자열을 한 문자 단위로 분해하여 tree를 만들어 검색을 빠르게 만들어 주는 자료구조
  • 문자열을 다루는 경우 많이 사용
  • 문자열의 길이가 M인 문자열이 N개가 있고 정렬되어 있을 때, 특정 문자열이 N개의 set에 포함 되는지 아닌지 알아 보는 문제.  이 경우 보통 이진탐색을 떠올리는데 이는 시간복잡도가 O(MlgN)이다. 하지만 Trie를 사용하면 O(M)의 시간복잡도로 검색
  • 구조 참조 : https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4
    • 루트는 빈 노드
    • 부모 노드에 접미 문자 하나씩을 붙여서 자식 노드를 생성
    • 간선은 접미 문자가 붙는 것을 나타냄
    • 종료노드 표시가 필요. basement의 경우 base에서 끝날 수도, basement에서 끝날 수도
  • Trie 사용해야하는 이유 : 문자열은 정수 실수와 달리 그 길이가 변하기 때문에 검색에 시간이 많이 걸림. 정수 실수의 경우 O(lgN)에 가능한데 문자열은 O(MlgN)이 필요. 많은 문자열을 다루는 문제에서는 거의 Trie를 사용해야만 제한된 시간 안에 정답이 나옴

 

#include <iostream>
using namespace std;

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE 26 //a~z
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
//only use lower case Alhpabet

struct NODE {
    bool isEnd;
    NODE* child[ALPHABET_SIZE];
}a[10000];

struct TRIE {
    NODE* root;
    int count;
}b[10000];

int idx_node = 0;
int idx_trie = 0;
TRIE* trie;

NODE* myNODEalloc() {
    return &a[idx_node++];
}

TRIE* myTRIEAlloc() {
    return &b[idx_trie++];
}

void insert(char* key) {
    //원래 없던 경우는 만들어짐
    //이미 있던 경우는 leaf node 체크가 됨 ex) "BET"가 있는데 "BE"가 들어오는 경우
    int length = strlen(key);
    trie->count++;

    NODE* p = trie->root;  //일단 루트 노드를 가리키게함

    //단어 길이만큼 레벨을 내려가며 노드 추가해줌
    for (int level = 0; level < length; ++level) {
        int index = CHAR_TO_INDEX(key[level]);

        if (!p->child[index]) {//비어 있으면
            p->child[index] = myNODEalloc();//노드 추가
        }
        //추가 해준 노드로 내려감
        p = p->child[index];
    }

    //들어온 key값의 마지막 글자에는 끝이라는 표시를 
    p->isEnd = true;
}

int search(char* key) {
    int length = strlen(key);
    NODE* p = trie->root;
    for (int level = 0; level < length; ++level) {
        int index = CHAR_TO_INDEX(key[level]);
        if (!p->child[index]) {
            return 0;//없으면 실패
        }
        //있으면 따라 내려감
        p = p->child[index];
    }
    return (p->isEnd);//isEnd 단어 끝이라 표시 되어있어야 됨
}

int main(void) {
    int T; cin >> T;
    for (int test_case = 0; test_case < T; ++test_case) {
        //init
        idx_node = 0;
        idx_trie = 0;

        trie = myTRIEAlloc();
        trie->count = 0;
        trie->root = myNODEalloc();

        char key[][8] = { "the", "a", "there", "answer", "any","by","bye","their" };
        char output[][32] = { "Not present in trie", "Present in Trie" };

        for (int i = 0; i < ARRAY_SIZE(key); ++i) {
            insert(key[i]);
        }

        char Q[][10] = { "they","these","their","thaw","thei" };
        
        for (int i = 0; i < ARRAY_SIZE(Q); ++i) {
            printf("%s --- %s\n", Q[i], output[search(Q[i])]);
        }
        
    }

    return 0;
}

 

You may also like...