[자료구조]#8_Trie 검색 트리

 

#1. 개념

 

트라이(Trie)는 검색 트리의 일종으로, 주로 문자열 검색에 사용되는 자료구조입니다. 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크(배열 혹은 맵)를 가지고 있는 트리 자료구조 중 하나입니다. 

 

#2. 동작 방식

 

1. 검색

트라이 검색 트리에서 특정 문자열을 검색할 경우, 해당 문자열의 각 노드를 트라이 검색 트리의 루트 노드를 시작으로 순차적으로 탐색합니다. 만약, 해당 문자열의 각 문자를 나타내는 노드를 모두 성공적으로 찾고, 그 끝에 문자열의 끝을 나타내는 마커가 존재하면, 해당 문자열은 트라이 검색  트리에 존재합니다.

 

2. 삽입/삭제

트라이 검색 트리에 새로운 문자열을 삽입할 때, 트리의 루트 노드부 시작하여 각 문자에 해당하는 노드를 순차적으로 탐색합니다. 만약, 해당 문자를 나타내는 노드가 없다면, 새로운 노드를 생성합니다. 문자열의 마지막 문자까지 이 과정을 반복하고, 마지막 문자를 나태는 노드에 문자열의 마지막을 나타내는 Terminal 마커를 추가해 줍니다.

트라이 검색 트리의 기존 문자열을 삭제할 때, 먼저 해당 문자열의 마지막 문자를 나타내는 노드에서 Terminal 마커를 제거하고, 더 이상 사용하지 않는 노드를 검색 트리로부터 삭제해 줍니다.

 

3. 코드

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

// 트라이 노드 정의
struct TrieNode {
    unordered_map<char, TrieNode*> children; // 자식 노드를 저장하기 위한 맵
    bool isEnd; // 단어의 끝을 표시하는 플래그
    TrieNode() : isEnd(false) {} // 생성자
};

// 트라이 클래스 정의
class Trie {
private:
    TrieNode* root; // 루트 노드

public:
    Trie() {
        root = new TrieNode(); // 루트 노드 생성
    }

    // 단어 삽입 메서드
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode(); // 새로운 자식 노드 생성
            }
            node = node->children[ch]; // 다음 노드로 이동
        }
        node->isEnd = true; // 단어의 끝임을 표시
    }

    // 단어 검색 메서드
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                return false; // 해당 문자를 나타내는 자식 노드가 없으면 단어가 없음
            }
            node = node->children[ch]; // 다음 노드로 이동
        }
        return node->isEnd; // 단어의 끝인지 확인하여 반환
    }
};

 

---