[c++] 트라이를 이용한 검색

15 Dec 2023

트라이(Trie)는 문자열을 저장하고 검색하는 데 사용되는 트리 자료 구조입니다. 이 자료 구조는 일반적으로 문자열 검색 및 자동 완성 기능을 구현하는 데 유용합니다. C++에서는 트라이를 활용하여 효율적으로 문자열을 검색할 수 있습니다.

트라이(Trie)란?

트라이(Trie)는 각 노드가 문자를 나타내고, 각 경로가 글자열을 나타내는 트리 자료 구조입니다. 이 자료 구조를 사용하면 문자열을 저장하고 검색하는 데 O(m)의 시간복잡도를 가질 수 있습니다. 여기서 m은 문자열의 길이입니다. 이는 일반적인 해시 테이블이나 이진 검색 트리에 비해 훨씬 빠른 검색 시간을 제공합니다.

C++에서 트라이 사용하기

다음은 C++에서 트라이를 사용하여 문자열을 검색하는 간단한 예제입니다.

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

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c];
        }
        curr->isEndOfWord = true;
    }

    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndOfWord;
    }

private:
    TrieNode* root;

    TrieNode* searchPrefix(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                return nullptr;
            }
            curr = curr->children[c];
        }
        return curr;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    cout << trie.search("apple") << endl;   // Output: 1 (true)
    cout << trie.search("app") << endl;     // Output: 0 (false)
    return 0;
}

이 예제에서는 C++의 unordered_map을 사용하여 각 노드의 자식 노드를 저장합니다. 이를 통해 문자열을 효율적으로 저장하고 검색할 수 있습니다.

마치며

C++에서 트라이를 사용하면 문자열을 효율적으로 저장하고 검색할 수 있습니다. 이를 통해 문자열 기반의 다양한 응용프로그램을 구현할 수 있습니다.

참고 문헌: