[c++] 트라이(Trie) 구조

12 Dec 2023

트라이는 검색 트리의 일종으로, 문자열 검색과 접두사 검색을 효과적으로 수행할 수 있는 자료 구조입니다. 트라이는 특히 문자열에서 접두사를 빠르게 찾아야 하는 경우에 유용합니다.

트라이 구조란?

트라이는 문자열을 저장하는 트리 형태의 자료구조로, 각 노드는 문자를 나타내는 값과 다음 문자를 가리키는 포인터로 구성됩니다. 뿐만 아니라, 각 노드에는 해당 문자열이 끝나는 지점인지를 나타내는 플래그도 포함됩니다.

트라이는 문자열을 순회하고 삽입하며, 주어진 문자열을 빠르게 찾을 수 있는 효율적인 방법을 제공합니다.

예시 코드

아래는 C++ 언어로 구현된 간단한 트라이 자료 구조의 예시 코드입니다.

#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
public:
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie* trie = new Trie();
    trie->insert("apple");
    cout << trie->search("apple") << endl;   // 출력: 1 (참)
    cout << trie->search("app") << endl;     // 출력: 0 (거짓)
    return 0;
}

요약

트라이(Trie) 구조는 문자열 검색과 접두사 검색을 빠르게 수행할 수 있는 자료구조입니다. 이 자료구조는 문자열 관련 작업에 효율적으로 활용될 수 있으며, 위 예시 코드를 통해 이해 및 구현할 수 있습니다.

참고 자료