트라이 알고리즘이란 ? (feat.cpp)

 

목차

• 트라이 란?
• 구현 - alpabet 소문자 기준
• 전체 코드
• 테스트 코드

 

트라이 란?

 

문자열 탐색을 보다 효율적으로 하기 위해 고안된 알고리즘입니다

단순하게 문자열을 비교해 나가면(brute force) 문자열 길이가 길어질수록 수행 시간이 오래 걸립니다..

반면 트라이 알고리즘은 트리 형태로 문자열을 정리해놓아 탐색 시 빠르게 탐색할 수 있습니다.

단. 트라이 알고리즘은 문자열의 길이가 길어질수록 트리의 깊이도 깊어지므로 공간 복잡도가 안 좋습니다.

아래 사진은 tree라는 문자열을 Insert 하는 과정입니다.

 

구현 - alpabet 소문자 기준

 

1. 트라이 클래스 생성

 

node : 자식 노드를 가리키는 변수(다음 문자를 가리킨다.)

check_end_str : 문자열의 마지막인지 아닌지 체크하는 변수

 

#define MAX_TRIE_SIZE 26

class Trie{
public :
    Trie * node[MAX_TRIE_SIZE];
    bool check_end_str;
    
    Trie(){
    	fill(node, node + MAX_TRIE_SIZE, nullptr);
        check_end_str = false;
    }
    
    ~Trie(){
        for(int i = 0; i < MAX_TRIE_SIZE; ++i)
            if(node[i] != nullptr)
                delete node[i];
    }
    ...
};

 

2. INSERT()

 

위에서 노드를 보면 26개의 배열로 만들어졌습니다.(알파벳 개수는 26개)

즉, a문자는 node [0], b문자는 node [1]... z문자는 node [25]에 값을 할당해 주기 위함입니다.

그러기 위해서는 알파벳을 노드의 인덱스로 바꾸어 주어야 합니다.

 

class Trie{
    ...
    int translate_index(const char c){
        return c - 'a';
    }
    ...
};

 

입력받은 문자가 마지막('\0')  일 시 check_end_str을 true 바꾸어 마지막임을 표시합니다.

마지막 문자에 도달할 때까지 노드를 만들거나 기존 노드를 타고 이동합니다.

 

class Trie{
    ...
    void insert(const char * str){
        if(*str == '\0'){
            check_end_str = true;
        }else{
            const int index = translate_index(*str);
            
            if(node[index] == nullptr)
                node[index] = new Trie();
            node[index]->insert(str + 1);
        }
    }
    ...
}

 

2. find()

트라이 탐색은 INSERT와 다른 점은 반환하는 값이 있다는 것뿐입니다.

마지막 문자열까지 도달했을 경우 문자열을 찾은 것이니 true을 리턴,

만약 마지막 문자열이 아니지만 해당 노드가 비어있다면 false를 리턴하도록 하겠습니다.

 

class Trie{
    ...
    bool find(const char * str){
        if(*str == '\0') 
            return true;
        
        const int index = translate_index(*str);
        
        if(node[index] == nullptr) 
            return false;
           
        node[index]->find(str + 1);
    }
    ...
}

 

전체 코드

 

#include <iostream>
#include <algorithm>
#define MAX_TRIE_SIZE 26

using namespace std;

class Trie{
public : 
    Trie * node[MAX_TRIE_SIZE];
    bool check_end_str;
    
     Trie(){
    	fill(node, node + MAX_TRIE_SIZE, nullptr);
        check_end_str = false;
    }
    
    ~Trie(){
        for(int i = 0; i < MAX_TRIE_SIZE; ++i)
            if(node[i] != nullptr)
                delete node[i];
    }

    int translate_index(const char c){
        return c - 'a';
    }

    void insert(const char * str){
        if(*str == '\0'){
            check_end_str = true;
        }else{
            const int index = translate_index(*str);
            
            if(node[index] == nullptr)
                node[index] = new Trie();
            node[index]->insert(str + 1);
        }
    }

    bool find(const char * str){
        if(*str == '\0') 
            return true;
        
        const int index = translate_index(*str);
        
        if(node[index] == nullptr) 
            return false;
           
        node[index]->find(str + 1);
    }

};

 

테스트 코드 (필요하신 분만)

 

words : trie에 저장할 문자열 목록

find_words : 탐색할 문자열 목록

int main(){
    Trie * trie = new Trie();

    const vector<string> words = {
        "apple", "tree", "word", "fire", "egg", "people", "number",
        "py", "google", "naver", "daum", "tistory"
    };
    
    const vector<string> find_words = {
        "apple", "tr", "google", "go", "whole", "find", "num",
        "good", "job", "peo", "never", "naver", "py", "pi"  
    };

    // insert 
    for(auto & word : words){
        trie->insert(word.c_str());
    }

    for(auto & find_word : find_words){
        cout << find_word;
        if(trie->find(find_word.c_str()))
            cout << " is!!!";
        else
            cout << " isn't...";
        cout << endl;
    }    
    return 0;
}