자료구조: Trie(자료구조)

Trie(트라이)는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반 자료구조이다.

트라이 자료구조는 특히 문자열 집합에서 특정 문자열을 빠르게 검색하거나 공통 접두사(prefix)를 찾는 데 효율적이다.

 

1. Trie의 기본 구조

Trie는 트리와 유사한 구조를 가지며, 각 노드는 하나의 문자 또는 값을 나타낸다. 

• 루트 노드(Root Node): Trie의 시작점으로, 비어 있는 상태로 시작한다.
• 자식 노드(Children Nodes): 각 노드는 자식 노드를 가질 수 있으며, 자식 노드는 해당 문자로 이어지는 문자열을 나타낸다.
• 말단 노드(Terminal Node): 특정 문자열의 끝을 표시하는 노드이다. 보통 플래그나 특수한 값을 사용하여 말단 노드를 표시한다.

2. Trie의 주요 연산

• 삽입(Insert): Trie에 새로운 문자열을 삽입한다.
• 검색(Search): Trie에서 특정 문자열이 존재하는지 확인한다.
• 삭제(Delete): Trie에서 특정 문자열을 제거한다.
• 접두사 검색(Prefix Search): 특정 접두사로 시작하는 모든 문자열을 찾는다.

3. Trie의 장점

• 빠른 검색: 문자열의 길이에 비례하는 검색 시간복잡도 O(m)을 가지며, 이는 해시 테이블과 달리 충돌이 없다는 장점이 있다.
• 공통 접두사 처리: 문자열 간의 공통 접두사를 공유하여 메모리를 효율적으로 사용할 수 있다.

4. Trie의 단점

• 메모리 사용량: 각 문자마다 노드를 생성하므로, 메모리 사용량이 많아질 수 있다. 특히, 자식 노드가 많은 경우 메모리 낭비가 발생할 수 있다.
• 복잡한 구현: 다른 단순한 자료구조에 비해 구현이 상대적으로 복잡하다.

5. Trie의 시간 복잡도

• 삽입(Insert): O(m) - m은 삽입할 문자열의 길이
• 검색(Search): O(m) - m은 검색할 문자열의 길이
• 삭제(Delete): O(m) - m은 삭제할 문자열의 길이

6. Trie의 구현

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

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

    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

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

    // 문자열 삽입
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }

    // 문자열 검색
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEndOfWord;
    }

    // 접두사 검색
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

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

7. 예시 문제

https://www.acmicpc.net/problem/16934

https://www.acmicpc.net/problem/5052