Trie 자료구조

개요

Trie(트라이, Prefix Tree)는 문자열 집합을 저장하고 접두사 기반으로 탐색하는 트리 자료구조입니다. 해시맵보다 접두사 검색이 빠르고, BST보다 문자열 비교가 적습니다. 게임에서는 채팅 필터링, 아이템 이름 자동완성, 커맨드 파서, 애니메이션 상태 이름 조회 등에 활용됩니다.

---

1. 기본 구조

"cat", "car", "card", "care", "dog" 삽입 결과:

root
├── c
│   └── a
│       ├── t (*)      "cat"
│       └── r (*)      "car"
│           ├── d (*)  "card"
│           └── e (*)  "care"
└── d
    └── o
        └── g (*)      "dog"

(*) = 단어 끝 표시

---

2. C++ 구현

2.1 배열 기반 Trie (고정 알파벳)

#include <array>
#include <string>
#include <memory>
#include <vector>

class Trie
{
    struct Node
    {
        std::array<std::unique_ptr<Node>, 26> children{};
        bool isEnd = false;
    };

    std::unique_ptr<Node> _root;

    static int ToIndex(char c) { return c - 'a'; }

public:
    Trie() : _root(std::make_unique<Node>()) {}

    void Insert(std::string_view word)
    {
        Node* cur = _root.get();
        for (char c : word)
        {
            int idx = ToIndex(c);
            if (!cur->children[idx])
                cur->children[idx] = std::make_unique<Node>();
            cur = cur->children[idx].get();
        }
        cur->isEnd = true;
    }

    bool Search(std::string_view word) const
    {
        const Node* cur = _root.get();
        for (char c : word)
        {
            int idx = ToIndex(c);
            if (!cur->children[idx]) return false;
            cur = cur->children[idx].get();
        }
        return cur->isEnd;
    }

    bool StartsWith(std::string_view prefix) const
    {
        const Node* cur = _root.get();
        for (char c : prefix)
        {
            int idx = ToIndex(c);
            if (!cur->children[idx]) return false;
            cur = cur->children[idx].get();
        }
        return true; // 노드가 존재하면 접두사 존재
    }
};

2.2 자동완성 구현

class AutocompleteTrie : public Trie
{
    struct Node
    {
        std::unordered_map<char, std::unique_ptr<Node>> children;
        bool isEnd = false;
        std::string word; // 단어 끝 노드에 전체 단어 저장
    };

    std::unique_ptr<Node> _root = std::make_unique<Node>();

    void DFS(const Node* node, std::vector<std::string>& results, int limit) const
    {
        if (results.size() >= static_cast<size_t>(limit)) return;
        if (node->isEnd) results.push_back(node->word);
        for (const auto& [ch, child] : node->children)
            DFS(child.get(), results, limit);
    }

public:
    void Insert(const std::string& word)
    {
        Node* cur = _root.get();
        for (char c : word)
        {
            if (!cur->children.count(c))
                cur->children[c] = std::make_unique<Node>();
            cur = cur->children[c].get();
        }
        cur->isEnd = true;
        cur->word  = word;
    }

    std::vector<std::string> Autocomplete(
        std::string_view prefix, int limit = 10) const
    {
        const Node* cur = _root.get();
        for (char c : prefix)
        {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return {}; // 접두사 없음
            cur = it->second.get();
        }

        std::vector<std::string> results;
        DFS(cur, results, limit);
        return results;
    }
};

// 사용
AutocompleteTrie trie;
for (const auto& item : {"sword", "shield", "staff", "spear", "stone"})
    trie.Insert(item);

auto suggestions = trie.Autocomplete("st");
// {"staff", "stone"} (또는 삽입 순서에 따라 다름)

---

3. 시간/공간 복잡도

연산	시간 복잡도	설명
Insert	O(L)	L = 문자열 길이
Search	O(L)
StartsWith	O(L)
Autocomplete	O(L + K)	K = 결과 수
공간	O(N × A)	N = 노드 수, A = 알파벳 크기

해시맵 기반 자식 저장은 공간 효율이 높지만 캐시 미스가 많습니다. 알파벳이 고정(소문자 26자)이고 데이터가 밀집하면 배열 기반이 더 빠릅니다.

---

4. Compressed Trie (Radix Tree)

연속되는 단일 자식 노드를 하나로 압축해 공간을 절약합니다.

일반 Trie:  r→e→a→d (4노드)
Radix Tree: "read" (1노드에 문자열 저장)

struct RadixNode
{
    std::string prefix;          // 압축된 접두사 문자열
    bool isEnd = false;
    std::unordered_map<char, std::unique_ptr<RadixNode>> children;
};

Radix Tree는 IP 라우팅 테이블, 파일 시스템 경로 조회에 주로 사용됩니다.

---

5. 게임에서의 활용 사례

5.1 채팅 금칙어 필터

class ProfanityFilter
{
    Trie _trie;

public:
    ProfanityFilter(const std::vector<std::string>& badWords)
    {
        for (const auto& w : badWords)
            _trie.Insert(w);
    }

    bool Contains(const std::string& text) const
    {
        std::string lower = text;
        std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);

        for (size_t i = 0; i < lower.size(); i++)
            if (_trie.StartsWith(lower.substr(i))) return true;
        return false;
    }
};

5.2 커맨드 파서

// 콘솔 커맨드 자동완성
AutocompleteTrie cmdTrie;
for (const auto& cmd : {
    "god", "noclip", "give", "kill", "teleport",
    "timescale", "fov", "quit"})
    cmdTrie.Insert(cmd);

// 사용자가 "g" 입력
auto cmds = cmdTrie.Autocomplete("g");
// {"god", "give"}

---

요약

• Trie는 문자열 집합의 접두사 탐색을 O(L) 시간에 수행한다. 해시맵은 정확한 키 탐색에 강하지만 접두사 쿼리에는 Trie가 우월하다.
• 알파벳 크기가 고정이면 array<Node*, 26> 배열 기반, 유니코드처럼 가변이면 unordered_map<char, Node*> 해시 기반을 사용한다.
• 공간 효율이 중요하면 단일 자식 체인을 압축하는 Radix Tree를 검토한다.
• 게임에서는 자동완성, 금칙어 필터, 커맨드 파서, 애셋 이름 조회 등에 실용적으로 활용된다.