C++로 구현하는 자료구조 (9) - Trie

C++로 구현하는 자료구조

이번 포스팅에서는 트라이에 대해 알아보려고 한다. 생소한 이름 때문에 어떤 역사가 있는 지 찾아봤더니 재미있는 일화가 있었다. 트라이는 René de la Briandais에 의해 개념이 소개되고, Edward Fredkin에 의해 reTRIEval(검색)이라는 단어에서 trie라고 명명되었다. 처음 발음할 때에는 트리라고 불러졌는데, 트리(tree)와 구분하기 위해서 트라이로 발음하기 시작했다고 한다. 그럼 어떤 자료구조인지 자세히 알아보자.

 

---

1. Trie

출처: https://www.geeksforgeeks.org/trie-insert-and-search/

트라이는 문자열을 빠르게 검색하기 위해 고안되었다. 기본적인 구조는 트리와 비슷한데 차이점은 노드에 문자열을 문자단위로 분해하여 저장한다는 점이다. 위의 그림과 같이 한 글자씩 트리를 따라가며 검색을 하는 구조이다. 한 글자씩 저장하지 않고 트라이의 초반부에서 접두사를 저장해놓으면 더욱 효율적인 검색도 가능하다.

 

 

2. Trie 구현방법

간단하게 trie를 구현하는 방법은 트리 구조를 따라가면서 노드를 생성할 때 알파벳 개수만큼의 nullptr을 연결해 주는 것이다. 이렇게하면 단어를 삽입할 때에 없는 문자일 때에만 메모리 할당이 일어난다. 탐색을 할 때에는 문자열을 순회하면서 노드를 따라가기만 하면 된다.

이렇게 문자열에 따라 트라이의 노드를 따라가기만 하면 되는 구조이기 때문에 시간복잡도는 굉장히 빠르다. 탐색하고자 하는 문자열의 길이가 m 이라면 트라이에서 이 문자를 검색하는 데에 걸리는 시간복잡도는 O(m)이 된다.

 

 

3. 소스코드

#pragma once
#include <iostream>
#include <vector>

#define ALPHABET_SIZE 26

class Node {
public:
    bool isEnd;
    Node* container[ALPHABET_SIZE];
    Node() {
        for (int idx = 0; idx < ALPHABET_SIZE; idx++) {
            this->container[idx] = nullptr;
        }
    }
};

class Trie {
private:
    Node* root;
public:
    Trie() {
        this->root = new Node();
    }

    void insert(const std::string& target) {
        Node* cursor = this->root;
        for (char element : target) {
            if (!cursor->container[element - 'a']) {
                cursor->container[element - 'a'] = new Node();
            }
            cursor = cursor->container[element - 'a'];
        }
        cursor->isEnd = true;
    }

    bool search(const std::string& target) {
        bool result = true;
        Node* cursor = this->root;
        for (char element : target) {
            if (!cursor->container[element - 'a']) {
                result = false;
                break;
            }
            cursor = cursor->container[element - 'a'];
        }
        if (!cursor->isEnd) {
            result = false;
        }

        return result;
    }

};

#include <iostream>
#include <string>

#include "datastructure/Trie.h"

int main() {

    Trie* trie = new Trie();
    trie->insert("abd");
    trie->insert("bcd");
    trie->insert("hello");

    std::cout << std::boolalpha;
    std::cout << trie->search("abd") << std::endl; // true
    std::cout << trie->search("abc") << std::endl; // false
    std::cout << trie->search("hello") << std::endl; // true

    return 0;
}