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

08 Dec 2023

트라이는 특히 문자열을 저장하고 검색하는 데 사용되는 트리 기반의 데이터 구조입니다. 트라이는 각 노드가 키의 한 문자를 나타내며, 루트부터 해당 키까지의 경로는 키의 문자들을 나타냅니다.

트라이의 구조

트라이의 각 노드는 문자와 자식 노드에 대한 포인터로 구성됩니다. 일반적으로 트라이는 루트 노드에서 시작하여 하위 노드로 이어지는 경로로 구성됩니다. 각 노드는 일반적으로 알파벳 문자의 경우 26개의 자식 노드를 가질 수 있습니다.

코드 예시

다음은 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* current = root;
            for(char c : word) {
                if(current->children.find(c) == current->children.end()) {
                    current->children[c] = new TrieNode();
                }
                current = current->children[c];
            }
            current->isEndOfWord = true;
        }
        
        bool search(string word) {
            TrieNode* current = root;
            for(char c : word) {
                if(current->children.find(c) == current->children.end()) {
                    return false;
                }
                current = current->children[c];
            }
            return current->isEndOfWord;
        }
};

int main() {
    Trie* trie = new Trie();
    trie->insert("hello");
    cout << trie->search("hello") << endl;  // Output: 1 (True)
    cout << trie->search("world") << endl;  // Output: 0 (False)
    return 0;
}

요약

트라이는 문자열 검색 및 삽입 연산에서 빠른 성능을 보장하는 자료 구조입니다. 트라이는 딕셔너리나 검색 엔진과 같이 문자열을 처리해야 하는 많은 애플리케이션에서 사용됩니다.

참고 자료:

이상으로 트라이 데이터 구조에 대한 간단한 소개였습니다. 부디 도움이 되셨기를 바랍니다!