[Week03] Trie

Trie

Trie(트라이)는 문자열 검색을 빠르게 수행하기 위해 사용하는 트리(Tree) 기반의 자료구조이다. 주로 자동 완성(Autocomplete), 사전(Dictionary) 구현, 문자열 검색(String Matching) 등의 문제를 해결하는 데 활용된다.

[출처] 위키백과

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.
• 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다.
• 예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다.
• [출처] [자료구조] 트라이 (Trie)

Trie의 특징

• 노드(Node) 기반 구조: 각 노드는 문자를 저장하며, 루트에서부터 자식 노드들을 따라가며 문자열을 표현한다.
• 빠른 검색 속도: O(M) (M은 검색하려는 문자열의 길이)으로 검색 가능하다.
• 중복 최소화: 같은 접두사를 가지는 단어들이 공통된 노드를 공유하여 메모리를 절약할 수 있다.
• 해시 테이블과의 차이점: 해시 테이블은 키의 길이에 상관없이 O(1)의 평균 검색 시간을 가지지만, 충돌 문제와 정렬 기능이 없다. Trie는 키의 길이에 비례한 검색 시간이 걸리지만, 사전순 탐색(lexicographical order) 기능이 가능하다.

Trie 기본 연산

삽입 (Insertion)

새로운 문자열을 삽입할 때, 문자열의 각 문자를 Trie의 노드를 따라가면서 저장한다. 만약 해당 문자가 존재하지 않는다면 새로운 노드를 생성한다.

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

검색 (Search)

입력한 문자열이 Trie에 존재하는지 확인하는 연산이다. 단어의 마지막 노드가 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

삭제 (Deletion)

문자열을 Trie에서 제거하는 연산이다. 단어의 마지막 노드가 다른 단어의 일부가 아니라면 해당 노드를 삭제한다.

def delete(self, word):
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end_of_word:
                return False
            node.is_end_of_word = False
            return len(node.children) == 0
        
        char = word[depth]
        if char not in node.children:
            return False
        
        should_delete = _delete(node.children[char], word, depth + 1)
        if should_delete:
            del node.children[char]
            return len(node.children) == 0
        return False
    
    _delete(self.root, word, 0)

Trie의 활용 예시

• 자동 완성 기능: 사용자가 입력한 단어의 접두사를 기반으로 추천 단어 목록을 제공
• 사전(Dictionary) 검색: 문자열이 존재하는지 빠르게 탐색 가능
• IP 주소 저장 및 검색: 라우팅 테이블에서 주소를 빠르게 검색하는 데 사용
• DNA 서열 분석: 유전체 데이터에서 특정 패턴을 탐색하는 데 유용

Trie의 장점과 단점

✅ 장점

• 문자열 검색이 빠르다 (O(M))
• 중복된 접두사를 공유하여 공간을 절약할 수 있다
• 사전순 정렬이 가능하다

❌ 단점

• 저장 공간을 많이 차지할 수 있음 (특히, 사용되지 않는 노드가 많아지면 메모리 낭비 발생)
• 구현이 다소 복잡함

정리

Trie는 문자열을 다루는 문제에서 매우 강력한 도구이며, 검색과 자동 완성 같은 기능을 최적화하는 데 유용하다. 하지만 공간 복잡도를 고려해야 하며, 실제 프로젝트에서는 Ternary Search Tree 또는 Compressed Trie 같은 변형 구조도 고려할 필요가 있다.