CS/자료구조

[자료구조](17)[trie]

황올뱀 2025. 5. 20. 19:57

 

trie

자동완성 등에 특화된 자료구조
-> 접두사를 기준으로 빠른 탐색 가능

 

그냥 배열 vs trie

  • 단어 탐색: N개의 단어가 있을 때 L길이의 단어를 찾는다면
        배열: N개의 단어에 대해 L길이만큼 다 맞는지 확인 -> O(LN)
        trie: 단어 길이만큼만 분기를 따라가면 됨 -> O(L)
  • 접두사 탐색: P길이의 접두사가 주어지고 N개의 단어 중 찾는다면
        배열: P길이의 접두사 비교를 N개의 단어에 대해 모두 확인 -> O(PN)
        trie: 얘도 접두사 만큼만 따라가면 됨 -> O(P) (= O(L))
  • 메모리 차지
        배열은 그냥 저장하면 되지만
        trie는 노드별로 분기를 저장해야 되기 때문
        예) 영어를 저장하는 trie는 각 노드마다 26개의 공간이 있어야 한다.
            <- 물론 자식이 생길 때마다 포인터 공간을 동적할당하는 경우도 있는데 전통적인 trie에선 아님
  • 이식성
    당연히 배열이 훨-씬 쉬움

 

구현

 

기본 골조

이진트리랑 다르게 자식을 가리키는 포인터가 (영어 기준)26개나 된다.
그리고 isEndOfWord라는 값이 추가로 더 필요하다.
왜냐하면 접두사가 같은 다른 단어를 저장할 때 그 단어인지 판별하기 위해서이다.
예) car와 care이 저장되었다 하자.
    c - a - r - e
    이게 care 한 글자인지 car, care 두 글자인지 ca, car, care인지 끝이 지정되지 않았으면 알지 못함.
    따라서 r, e에 isEndOfWord로 표시를 해줘야 한다.

#define ALPHABET_SIZE 26

typedef struct TrieNode{
    struct TriNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

 

makeTrieNode

빈 TrieNode를 만든다.

TrieNode* makeTrieNode(){
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++){
        node->children[i] = NULL;
    }
    return node;
}

 

search

글자 하나하나 따라가며
글자가 있는가?
있긴 한데 그게 글자의 끝인가?
를 따짐

bool search(TrieNode* root, const char* word){
    TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++){ //글자 하나하나 따라가겠다는 뜻
        int index = word[i] - 'a';
        if (curr->children[index] == NULL) {return false;} //만약 따라갔는데 없다면?
        curr = curr->children[index];                      //다음 글자로 이동
    }
    return curr->isEndOfWord;         // 해당 글자가 있는가? & 글자의 끝인가? 체크
}

 

insert

단어의 한 글자씩 노드를 추가한다.

void insert(TrieNode** root, const char* word){
    TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++){ //단어의 끝까지 반복
        int index = word[i] - 'a';         //'a'를 빼서 문자를 인덱스로 바꾸기
        if (curr->children[index] == NULL){ 
            curr->children[index] = makeNode();
        }
        curr = curr->children[index];
    }
    curr->isEndOfWord = true; //마지막에 isEndOfWord를 true로 바꿔 마무리
}

 

delete

먼저 비어있는지 확인 후

bool isEmpty(TrieNode* root){
    for (int i = 0; i < ALPHABET_SIZE; i++){
        if (root->children[i]) {return false;}
    }
    return true;
}

지운다.

TrieNode* deleteWord(TrieNode* root, const char* word, int depth = 0){
    if (!root) {return NULL;} // 없는 경로면 바로 빠져나감
    if (word[depth] == '\0'){ // 단어의 끝인가?
        if (root->isEndOfWord) {root->EndOfWord = false} //단어의 끝을 해제하는 것으로 단어 지우기는 끝남
        if (isEmpty(root)){      //아무것도 없으면 바로 free
            free(root);
            return NULL;
        }
        return root;
    }
    // 만약 뒤에 단어가 더 남았으면
    int index = word[depth] - 'a';
    root->children[index] = delete(root->children[index], word, depth + 1);//재귀호출로 계속 지우기
    if (isEmpty(root) && !root->isEndOfWord){
        free(root);
        return NULL;
    }
    return root;
}
728x90
반응형