트라이(접두사 트리)란? 동작 원리, 코드, 시간 복잡도

트라이가 해결하는 문제

해시 집합은 "이 단어가 정확히 저장되어 있는가?"에는 빨리 답하지만, 모든 단어를 확인하지 않고는 "pre로 시작하는 저장된 단어는 무엇인가?"에 답할 수 없습니다. 정렬된 리스트는 이진 탐색으로 접두사 질의에 답할 수 있지만 삽입이 느립니다. 트라이는 접두사 단위로 구성되어 있으므로 접두사 질문이 본래 강점입니다. 검색창의 자동완성, 단어 게임, 맞춤법 검사, 네트워크 경로의 최장 접두사 일치가 그 예입니다.

쉬운 말로 설명하는 원리

글자를 하나씩 입력하며 좁혀 가는 휴대폰 연락처 목록을 떠올려 보세요. c를 입력하면 c로 시작하는 모든 사람이 나오고, ca를 입력하면 목록이 더 좁아지는 식입니다. 트라이는 단어를 바로 이런 모양으로 저장합니다. 루트는 빈 접두사입니다. 각 노드는 다음 문자에서 자식 노드로 가는 맵과 단어 끝 플래그를 가집니다. car 같은 단어는 완성된 단어이면서 동시에 cart의 접두사이기도 하기 때문입니다.

예제: car, cart, cat, dog 삽입하기

네 단어는 글자가 모두 13개지만 car, cart, cat이 ca를 공유하므로 루트 아래에는 노드가 8개(c, a, r, t, t, d, o, g)만 필요합니다. ca를 검색하면 노드 두 개를 지나 접두사로서는 성공하지만, 그 노드에 끝 표시가 없으므로 ca는 단어가 아닙니다. cow를 검색하면 두 번째 단계에서 실패합니다. 노드 c에 자식 o가 없기 때문입니다.

파이썬 구현

각 노드는 자식의 dict를 가지므로 유니코드를 포함한 어떤 문자 집합도 처리할 수 있습니다. starts_with 메서드는 접두사 아래의 모든 단어를 모으며, 이것이 자동완성의 핵심입니다.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with는 출력 순서를 일정하게 하려고 결과를 정렬합니다. 실제 자동완성은 처음 몇 개의 결과만 반환하고 멈춘 뒤, 저장된 인기도 같은 값으로 순위를 매기기도 합니다.

시간 복잡도와 공간 복잡도

시간이 단어 수 n에 의존하지 않는다는 점이 문자열 균형 트리(O(m log n)번의 비교)에 비한 가장 큰 장점입니다. 대가는 메모리입니다. 각 노드가 자기 딕셔너리를 가진 별도의 객체이므로 트라이는 원본 문자열보다 몇 배나 많은 메모리를 쓸 수 있습니다.

변형과 흔한 실수

• 배열 자식: 소문자 영어라면 26칸짜리 고정 배열을 씁니다. dict보다 빠르지만, 문자가 드문드문 쓰이거나 문자 집합이 크면 낭비가 큽니다.
• 압축 트라이(래딕스 트리, 파트리샤 트라이): 자식이 하나뿐인 노드의 체인을 문자열 레이블이 붙은 간선 하나로 합쳐 메모리를 크게 줄입니다. 래딕스 트리는 IP 라우팅 테이블과 일부 HTTP 라우터에 쓰입니다.
• 삼진 탐색 트리: 각 노드가 자식 세 개(작음, 같음, 큼)를 가지며, 넓은 배열보다 메모리를 적게 씁니다.
• 카운팅 트라이: 각 노드에 카운터를 저장하여 "이 접두사로 시작하는 단어가 몇 개인가?"에 O(m)으로 답합니다.
• 비트 트라이: 숫자를 비트 단위로 저장해 최대 XOR 문제를 풉니다.

트라이를 쓸 때와 면접 단골 문제

접두사 질의, 최장 접두사 일치, 접두사를 공유하는 많은 문자열의 정렬된 순회가 필요할 때 트라이를 사용하세요. 정확히 일치하는 조회만 필요하다면 set이나 dict를 쓰세요. 파이썬에서는 더 단순하고 메모리도 적게 씁니다. 작고 변하지 않는 단어 목록이라면 bisect 모듈과 정렬된 리스트로도 접두사 질의에 충분히 답할 수 있습니다.

대표 문제: 트라이 구현하기(삽입, 검색, 접두사 확인), 목표 단어가 많은 격자 단어 찾기, 단어를 가장 짧은 어근으로 바꾸기, 최장 공통 접두사, 검색 자동완성 시스템 설계, 비트 트라이를 이용한 두 수의 최대 XOR.