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"} (또는 삽입 순서에 따라 다름)

2.3 삭제(Delete) 구현

단어 삭제는 삽입의 역방향으로, 더 이상 다른 단어에 공유되지 않는 노드를 제거합니다.

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

        bool IsLeaf() const
        {
            for (const auto& c : children)
                if (c) return false;
            return true;
        }
    };

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

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

    // 재귀 삭제: true 반환 시 부모가 이 노드를 해제해야 함
    bool DeleteRecursive(Node* node, std::string_view word, int depth)
    {
        if (!node) return false;

        if (depth == (int)word.size())
        {
            // 단어 끝 도달
            if (!node->isEnd) return false; // 단어가 없음
            node->isEnd = false;
            // 자식이 없으면 이 노드를 삭제해도 됨
            return node->IsLeaf();
        }

        int idx = ToIndex(word[depth]);
        if (!node->children[idx]) return false;

        bool shouldDelete = DeleteRecursive(node->children[idx].get(), word, depth + 1);
        if (shouldDelete)
        {
            node->children[idx].reset(); // 자식 노드 해제
            // 현재 노드도 단어 끝이 아니고 자식이 없으면 삭제 가능
            return !node->isEnd && node->IsLeaf();
        }
        return false;
    }

public:
    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 Delete(std::string_view word)
    {
        return DeleteRecursive(_root.get(), word, 0);
    }
};

// 삭제 예시
void ExampleDelete()
{
    TrieWithDelete trie;
    trie.Insert("cat");
    trie.Insert("car");
    trie.Insert("card");

    trie.Delete("card"); // "card" 삭제: d 노드 제거, r 노드는 "car" 때문에 유지
    trie.Delete("car");  // "car" 삭제: r 노드 제거, a는 "cat" 때문에 유지

    bool hasCat  = trie.Search("cat");  // true
    bool hasCar  = trie.Search("car");  // false
    bool hasCard = trie.Search("card"); // false
}

---

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"}

5.3 에셋 이름 빠른 검색 — Unreal Engine 에셋 브라우저 패턴

대규모 프로젝트에서 수천 개의 에셋 이름을 접두사로 빠르게 검색합니다.

// 에셋 경로 Trie 인덱스
// "Textures/Characters/Hero_Body", "Textures/Characters/Hero_Face" 등 경로 저장
class UAssetNameIndex : public UGameInstanceSubsystem
{
    AutocompleteTrie _assetTrie;
    bool _built = false;

public:
    // 게임 시작 시 또는 에디터에서 에셋 목록 빌드
    void BuildIndex(const TArray<FString>& AssetPaths)
    {
        for (const FString& Path : AssetPaths)
        {
            std::string path(TCHAR_TO_UTF8(*Path.ToLower()));
            _assetTrie.Insert(path);
        }
        _built = true;
    }

    // 접두사로 에셋 검색 — O(L + K)
    TArray<FString> SearchByPrefix(const FString& Prefix, int32 MaxResults = 20) const
    {
        if (!_built) return {};

        std::string prefix(TCHAR_TO_UTF8(*Prefix.ToLower()));
        auto suggestions = _assetTrie.Autocomplete(prefix, MaxResults);

        TArray<FString> Results;
        for (const auto& s : suggestions)
            Results.Add(UTF8_TO_TCHAR(s.c_str()));
        return Results;
    }
};

5.4 Trie vs 해시맵 — 언제 어떤 것을 선택하는가

시나리오	권장 자료구조	이유
정확한 키로 값 조회	TMap / unordered_map	O(1) 평균, 구현 단순
접두사 검색·자동완성	Trie	O(L) 접두사 탐색, 해시맵으로 불가
여러 패턴 동시 검색	Aho-Corasick (Trie 확장)	단일 패스 O(N+출현수)
공간이 매우 제한적	Compressed Trie (Radix Tree)	단일 자식 체인 압축
유니코드 문자열	해시맵 기반 Trie	가변 알파벳 크기 처리

---

정리

연산	시간복잡도	비고
Insert	O(L)	L = 문자열 길이
Search	O(L)	정확한 단어 탐색
StartsWith	O(L)	접두사 존재 여부
Delete	O(L)	불필요한 노드 자동 해제
Autocomplete	O(L + K)	K = 결과 단어 수
공간	O(N × A)	N = 총 노드 수, A = 알파벳 크기

핵심 요약:

• Trie는 문자열 집합의 접두사 탐색을 O(L) 시간에 수행한다. 해시맵은 정확한 키 탐색에 강하지만 접두사 쿼리에는 Trie가 우월하다.
• 알파벳 크기가 고정(소문자 26자)이면 array<Node*, 26> 배열 기반이 캐시 효율 우수. 유니코드처럼 가변이면 unordered_map<char, Node*> 해시 기반을 사용한다.
• 삭제 시 공유되지 않는 노드를 재귀적으로 제거하여 메모리 누수를 방지해야 한다.
• 공간 효율이 중요하면 단일 자식 체인을 압축하는 Radix Tree(Compressed Trie)를 검토한다.
• 여러 패턴을 동시에 텍스트에서 탐색해야 한다면 Trie에 실패 링크를 추가한 Aho-Corasick 알고리즘으로 확장한다.
• 게임에서는 자동완성, 금칙어 필터, 커맨드 파서, 에셋 이름 인덱싱 등 접두사 기반 검색이 필요한 모든 시스템에 실용적으로 활용된다.