트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 문자열의 접두사를 공통으로 가지는 문자열들을 하나의 노드에 모아서 저장하는 방식으로 구성된다.

특징

• 각 노드는 문자 하나를 저장한다.
• 루트 노드는 비어있다.
• 각 간선(edge)은 추가될 문자를 나타낸다.
• 한 노드의 모든 자식 노드들은 서로 다른 문자를 가진다.

장점

• 문자열 검색이 매우 빠르다 - O(M) 시간 복잡도 (M은 문자열의 길이)
• 접두사를 이용한 검색이 효율적이다.
• 자동완성, 사전 검색 등에 적합하다.
• 문자열 집합을 효과적으로 표현할 수 있다.

단점

• 메모리 사용량이 많다 - 각 노드가 모든 가능한 문자에 대한 포인터를 가져야 한다.
• 구현이 상대적으로 복잡하다.
• 삽입과 삭제 연산이 해시 테이블보다 느릴 수 있다.

구현 방법

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: str) -> None:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True
    
    # 문자열 검색
    def search(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_end_of_word
    
    # 문자열 삭제
    def delete(self, word: str) -> bool:
        def _delete_helper(node: TrieNode, word: str, depth: int = 0) -> bool:
            # 문자열의 끝에 도달했을 때
            if depth == len(word):
                # 해당 노드가 단어의 끝이 아니면 False 반환
                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_current = _delete_helper(node.children[char], word, depth + 1)
            
            # 자식 노드를 삭제해야 하면
            if should_delete_current:
                del node.children[char]
                # 현재 노드가 다른 단어의 끝이 아니고 자식이 없으면 삭제 가능
                return len(node.children) == 0 and not node.is_end_of_word
            
            return False
        
        return _delete_helper(self.root, word)

삽입

루트 노드부터 시작하여 자식 노드들이 저장된 딕셔너리에서 삽입할 문자열을 한 문자씩 확인한다. 해당 문자가 없으면 새로운 노드를 추가하고, 있으면 그 노드로 이동한다.