[C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie)

트라이 (Trie)

트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.

트라이의 특징:

1. 노드 구조: 각 노드는 문자와 자식 노드를 가집니다.
2. 루트 노드: 루트 노드는 빈 문자열을 나타냅니다.
3. 경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.
4. 접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.

트라이 구현

TrieNode.h

#ifndef TRIENODE_H
#define TRIENODE_H

#include <unordered_map>

// 트라이의 노드 구조체
struct TrieNode {
    std::unordered_map<char, TrieNode*> children; // 자식 노드를 가리키는 맵
    bool isEndOfWord; // 단어의 끝을 나타내는 플래그

    TrieNode() : isEndOfWord(false) {}
};

#endif // TRIENODE_H

 

Trie.h

#ifndef TRIE_H
#define TRIE_H

#include "TrieNode.h"
#include <string>

class Trie {
public:
    Trie() : root(new TrieNode()) {} // 생성자
    ~Trie(); // 소멸자

    void insert(const std::string& word); // 단어 삽입
    bool search(const std::string& word) const; // 단어 검색
    bool startsWith(const std::string& prefix) const; // 접두사 검색

private:
    TrieNode* root; // 트라이의 루트 노드

    void destroy(TrieNode* node); // 트리 파괴 (재귀)
};

// 소멸자 정의 (메모리 해제)
Trie::~Trie() {
    destroy(root);
}

// 트리 파괴 함수 정의 (재귀)
void Trie::destroy(TrieNode* node) {
    if (node != nullptr) {
        for (auto& child : node->children) {
            destroy(child.second);
        }
        delete node; // 노드 메모리 해제
    }
}

// 단어 삽입 함수 정의
void Trie::insert(const std::string& word) {
    TrieNode* currentNode = root;
    for (char ch : word) {
        if (currentNode->children.find(ch) == currentNode->children.end()) {
            currentNode->children[ch] = new TrieNode(); // 새로운 노드 생성
        }
        currentNode = currentNode->children[ch]; // 다음 노드로 이동
    }
    currentNode->isEndOfWord = true; // 단어의 끝 표시
}

// 단어 검색 함수 정의
bool Trie::search(const std::string& word) const {
    TrieNode* currentNode = root;
    for (char ch : word) {
        if (currentNode->children.find(ch) == currentNode->children.end()) {
            return false; // 문자를 찾을 수 없음
        }
        currentNode = currentNode->children[ch]; // 다음 노드로 이동
    }
    return currentNode->isEndOfWord; // 단어의 끝인지 확인
}

// 접두사 검색 함수 정의
bool Trie::startsWith(const std::string& prefix) const {
    TrieNode* currentNode = root;
    for (char ch : prefix) {
        if (currentNode->children.find(ch) == currentNode->children.end()) {
            return false; // 문자를 찾을 수 없음
        }
        currentNode = currentNode->children[ch]; // 다음 노드로 이동
    }
    return true; // 접두사를 찾음
}

#endif // TRIE_H

 

트라이 예제

#include <iostream>
#include "Trie.h"

int main() {
    Trie trie;
    trie.insert("hello");
    trie.insert("world");
    trie.insert("hi");
    trie.insert("her");
    trie.insert("hero");

    std::cout << "hello 검색: " << (trie.search("hello") ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "world 검색: " << (trie.search("world") ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "her 검색: " << (trie.search("her") ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "hero 검색: " << (trie.search("hero") ? "찾음" : "찾지 못함") << std::endl;
    std::cout << "he 검색: " << (trie.search("he") ? "찾음" : "찾지 못함") << std::endl;

    std::cout << "he로 시작하는 단어 존재: " << (trie.startsWith("he") ? "예" : "아니오") << std::endl;
    std::cout << "wo로 시작하는 단어 존재: " << (trie.startsWith("wo") ? "예" : "아니오") << std::endl;
    std::cout << "ha로 시작하는 단어 존재: " << (trie.startsWith("ha") ? "예" : "아니오") << std::endl;

    return 0;
}

 

설명

1. 트라이 (Trie):
   • 트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다.
   • 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.
2. 트라이의 주요 연산:
   • 삽입 (Insert): 새로운 문자열을 트리에 삽입합니다.
   • 검색 (Search): 특정 문자열이 트리에 있는지 검색합니다.
   • 접두사 검색 (StartsWith): 특정 접두사로 시작하는 문자열이 트리에 있는지 검색합니다.

이제 트라이의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 11: 그래프의 기본 개념"에 대해 학습하겠습니다.