CS학습2026년 8월 18일

Trie: 문자열 검색 효율을 극대화하는 트리 기반 자료구조

Trie는 문자열을 키로 하는 자료구조로, 접두사를 공유하는 키들을 효율적으로 저장하고 검색할 수 있도록 설계되었다. 특히 자동 완성, 검색 제안, 철자 검사 등 문자열 기반의 작업에서 뛰어난 성능을 보인다. 각 노드는 하나의 문자를 나타내며, 루트 노드부터 시작하여 문자열을 따라 내려가면서 검색을 수행한다.

송민성3분 읽기

1. 개념

Trie(트라이, 발음은 “트라이”)는 tree(트리)와 비슷하지만 키가 문자열인 트리 기반의 자료구조이다. 때로는 prefix tree(프리픽스 트리)라고도 불린다. 각 노드는 단일 문자를 나타내고, 루트 노드부터 시작하여 문자열을 따라 내려가면서 검색을 수행한다. 노드는 문자 자체, 그리고 자식 노드에 대한 포인터를 포함한다.

2. 왜 사용하는가

효율적인 접두사 검색: Trie는 접두사를 공유하는 문자열을 효율적으로 검색할 수 있다. 이는 자동 완성, 검색 제안 등에 유용하다.
공간 효율성: 접두사를 공유하는 문자열은 중복 저장되지 않으므로, 공간 효율성이 높다.
알파벳 순서 기반 검색: Trie는 알파벳 순서대로 문자열을 저장하므로, 순서 기반의 검색이 용이하다.

3. 동작 원리

Trie는 루트 노드부터 시작하여 검색 키의 각 문자에 해당하는 자식 노드를 따라 내려간다. 만약 해당 문자에 대한 자식 노드가 존재하지 않으면, 검색 키는 Trie에 존재하지 않는다는 의미이다. 모든 문자를 따라 내려갔지만 노드가 단말 노드(end-of-word marker)로 표시되지 않았다면 해당 키는 존재하지 않는다.

새로운 키를 삽입할 때는 루트 노드부터 시작하여 각 문자에 해당하는 노드를 생성하거나, 이미 존재하는 노드를 따라간다. 마지막 문자에 해당하는 노드를 단말 노드로 표시한다.

4. 코드 예제

python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

    def insert(self, word):
        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):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Example usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple"))  # Output: True
print(trie.search("app"))    # Output: True
print(trie.starts_with("app")) # Output: True
print(trie.search("banana")) # Output: False

5. 시간 복잡도 또는 성능 특성

삽입(Insert): O(k), k는 삽입하려는 문자열의 길이
검색(Search): O(k), k는 검색하려는 문자열의 길이
접두사 검색(Starts With): O(k), k는 검색하려는 접두사의 길이

Trie의 성능은 문자열의 길이에 비례하며, 문자열의 길이와 관계없이 일정한 시간 내에 검색이 가능하다는 장점이 있다. 하지만, 노드의 수가 많아질수록 메모리 사용량이 증가할 수 있다.

6. 실무 사용 사례

자동 완성(Autocomplete): 사용자가 입력하는 문자열을 기반으로 가능한 완성어를 제안
검색 제안(Search Suggestion): 사용자가 검색어를 입력할 때 관련 검색어를 제안
철자 검사(Spell Checker): 잘못된 철자를 수정하거나 제안
IP 라우팅(IP Routing): IP 주소를 기반으로 최적의 경로를 탐색
압축(Compression): LZW 압축 알고리즘 등

7. 주의할 점

메모리 사용량: 노드의 수가 많아질수록 메모리 사용량이 증가할 수 있다.
알파벳 크기: 알파벳 크기가 큰 경우(예: 유니코드) 노드 수가 기하급수적으로 증가할 수 있다.
단말 노드 처리: 단말 노드를 적절하게 관리하지 않으면, 잘못된 검색 결과가 발생할 수 있다.

8. 핵심 정리

Trie는 문자열 검색을 효율적으로 수행할 수 있는 트리 기반의 자료구조이다. 접두사를 공유하는 문자열을 저장하여 공간 효율성을 높이고, 자동 완성, 검색 제안, 철자 검사 등 다양한 응용 분야에 활용될 수 있다. 삽입, 검색, 접두사 검색 연산은 모두 O(k)의 시간 복잡도를 가지므로, 빠른 검색 속도를 요구하는 경우 유용하게 사용할 수 있다.