[c++] 트라이 구조체와 알고리즘

08 Dec 2023

트라이는 검색 트리의 한 형태로, 공통 접두어를 갖는 문자열을 저장하고 검색하는 데 사용되는 자료 구조입니다. 이 구조체는 주로 문자열 검색 및 자동 완성 기능을 구현하는 데 유용합니다. 이 글에서는 트라이의 개념, 구현, 그리고 활용에 대해 알아보겠습니다.

트라이의 개념

트라이는 각 노드가 하나의 문자를 나타내며, 루트 노드부터 자식 노드까지 경로를 따라가면 문자열을 구성하는 글자들을 나타내는 이진 트리입니다. 각 노드는 자식 노드로 현재 글자에 이어지는 글자들을 가지며, 이진 트리의 성질을 따라 노드들을 연결합니다.

예를 들어, “apple”, “app”, “ape”라는 단어를 저장하고자 한다면, 루트 노드로부터 “a” 노드에서 “p” 노드로, “p” 노드에서 “p” 노드로, “p” 노드에서 “l”, “e” 노드로 연결된다고 할 수 있습니다.

이러한 트라이 구조는 문자열 검색에 있어 효율적인데, 특히 공통 접두어가 많은 문자열을 다루는 경우에 유용합니다.

트라이의 구현

다음은 트라이를 C++로 구현한 예제 코드입니다.

#include <iostream>
#include <unordered_map>

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

class Trie {
public:
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }
    
    void insert(std::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(std::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;
    trie.insert("apple");
    trie.insert("ape");
    std::cout << trie.search("app") << std::endl;  // Output: 0 (false)
    std::cout << trie.search("apple") << std::endl;  // Output: 1 (true)
    return 0;
}

트라이 알고리즘의 활용

트라이는 문자열 검색뿐만 아니라, 문자열 자동 완성, 철자 교정, 규칙 기반 검색 등의 기능에서도 사용될 수 있습니다. 또한, 트라이는 문자열의 공통 접두어를 효율적으로 저장하므로, 이를 활용한 데이터 압축 알고리즘 등에서도 사용될 수 있습니다.

이처럼 트라이는 문자열을 저장하고 검색하는 데 효율적인 자료구조로, 다양한 응용 분야에서 활용될 수 있습니다. 이 글에서는 트라이의 개념, 구현, 그리고 활용에 대해 알아보았습니다.

목차

트라이의 개념

트라이의 구현

트라이 알고리즘의 활용