트라이(Trie) 자료구조 완벽해부 (문자열 검색, 자동완성)

우리가 구글이나 네이버 검색창에 '자'를 입력했을 때 '자료구조', '자바스크립트'와 같은 추천 검색어가 순식간에 나타나는 원리를 궁금해한 적이 있으신가요? 수백만 개의 단어 중에서 사용자가 입력한 패턴을 실시간으로 찾아내는 이 마법 같은 기술의 배후에는 트라이(Trie)라는 자료구조가 존재합니다. 'Retrieval(검색)'에서 이름을 따온 트라이는 문자열을 저장하고 효율적으로 탐색하는 데 특화된 접두사 트리(Prefix Tree)입니다. 이 글에서는 트라이가 왜 검색 엔진과 자동완성 시스템의 표준이 되었는지, 해시(Hash)나 이진 탐색 트리(BST)와 비교하여 어떤 기술적 우위를 가지는지 심층 분석합니다.

1. 트라이(Trie)의 구조와 핵심 개념

트라이는 문자열의 각 문자를 노드(Node)로 저장하여 트리 형태로 구성한 자료구조입니다. 일반적인 트리와 달리, 루트 노드는 비어 있으며 그 자식 노드부터 문자열의 첫 번째 문자가 시작됩니다. 가장 큰 특징은 "공통 접두사(Prefix)를 공유한다"는 점입니다.

1-1. 데이터 저장 방식의 효율성

예를 들어 "APPLE", "APPLY", "ACE" 세 단어를 저장한다고 가정해 봅시다.

공유: "APPLE"과 "APPLY"는 앞의 "APPL"까지 동일한 경로를 공유합니다. 즉, 중복된 문자를 별도의 메모리에 저장하지 않고 기존 노드를 재사용합니다.
분기: "APP" 다음 단계에서 'L'(APPLE)과 'Y'(APPLY)로 분기가 나뉩니다.
종료 플래그: 각 단어의 끝나는 지점에는 "여기서 단어가 끝남(IsEndOfWord)"이라는 표시를 남겨, "APP" 같은 부분 문자열과 실제 단어를 구분합니다.

2. 왜 트라이를 사용하는가? (시간 복잡도 분석)

문자열 검색에서 가장 흔히 비교되는 대상은 이진 탐색 트리(BST)와 해시 테이블입니다. 트라이의 진가는 문자열의 길이에 비례하는 압도적인 속도에서 드러납니다.

2-1. 검색 속도의 우위: O(L)

저장된 단어의 개수가 $N$개이고, 찾으려는 문자열의 길이가 $L$이라고 할 때 시간 복잡도를 비교해 보겠습니다.

이진 탐색 트리(BST): $O(L \log N)$. 총 단어 개수($N$)가 많아질수록 탐색 시간이 늘어납니다. 문자열 비교 자체에도 $L$만큼의 시간이 걸리기 때문입니다.
트라이(Trie): O(L). 저장된 단어가 1억 개든 100억 개든 상관없이, 오직 찾으려는 키워드의 길이($L$)만큼만 트리를 타고 내려가면 됩니다. 이것이 자동완성 시스템이 트라이를 채택하는 결정적인 이유입니다.

3. 트라이의 치명적 단점: 메모리 사용량

완벽해 보이는 트라이에도 "공간 복잡도"라는 치명적인 단점이 존재합니다. 속도를 얻는 대신 메모리(Memory)를 희생하는 구조이기 때문입니다.

3-1. 포인터 배열의 오버헤드

트라이의 각 노드는 다음 문자를 가리키기 위해 자식 노드들에 대한 포인터 배열을 가져야 합니다. 만약 영어 소문자만 처리한다면 각 노드마다 크기 26의 배열이 필요하지만, 대소문자, 숫자, 한글까지 포함한다면 노드 하나가 차지하는 메모리는 기하급수적으로 늘어납니다. 이를 해결하기 위해 실무에서는 Map을 사용하거나, 압축된 형태인 Radix Tree (Patricia Trie)를 사용하여 최적화를 수행합니다.

4. 파이썬(Python)으로 구현하는 자동완성 엔진

다음은 딕셔너리(Map)를 활용하여 메모리 효율을 높인 트라이의 구현 코드입니다. 단어 삽입(Insert), 검색(Search), 그리고 접두사 확인(StartsWith) 기능을 포함합니다.


class TrieNode:
    def __init__(self):
        # 자식 노드들을 저장하는 딕셔너리 (Key: 문자, Value: 노드)
        self.children = {}
        # 해당 노드에서 단어가 끝나는지 표시
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # 자식 노드가 없으면 새로 생성
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # 마지막 문자에 단어의 끝임을 표시
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        # 문자가 모두 존재하고, 단어의 끝 플래그가 True여야 함
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """
        자동완성 기능의 핵심: 해당 접두사로 시작하는 단어가 있는지 확인
        """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 사용 예시
trie = Trie()
trie.insert("apple")
trie.insert("app")

print(trie.search("apple"))   # True
print(trie.search("app"))     # True
print(trie.starts_with("ap")) # True (apple, app이 있으므로)
print(trie.search("ap"))      # False (ap라는 단어 자체는 저장 안 됨)

4-1. 코드 분석 (StartsWith 메서드)

위 코드에서 `starts_with` 메서드는 자동완성 기능의 기반이 됩니다. 사용자가 'ap'만 입력해도 `True`를 반환하므로, 이후 해당 노드 아래에 있는 모든 자식 노드(p-l-e, p)를 순회(DFS/BFS)하여 추천 검색어 목록을 사용자에게 보여줄 수 있습니다.

[핵심 요약 : 트라이(Trie) 자료구조]
1. 정의: 문자열의 접두사(Prefix)를 트리 구조로 저장하여 중복을 제거하고 탐색 효율을 높인 자료구조입니다.
2. 성능: 데이터의 양(N)과 무관하게 키워드 길이(L)에 비례하는 $O(L)$의 압도적인 검색 속도를 자랑합니다.
3. 활용: 검색 엔진의 자동완성, 맞춤법 검사기, IP 라우팅(Longest Prefix Match) 등 빠른 문자열 처리가 필수적인 분야에 사용됩니다.

kguidebook0001 님의 블로그