트라이(trie)

트라이는 문자열을 효율적으로 처리하기 위한 트리 자료구조

문자열을 문자 하나씩 쪼개서 노드에 저장, 한 노드의 경로가 문자열 하나를 의미

단어 S를 삽입, 탐색, 삭제를 모조리 O(|S|)에 처리할 수 있다

하지만 메모리를 아주 많이 차지한다는 단점이 있다

트리 구조로 앞에 중복되는 문자들이 있으면 그 뒤부터 새로운 노드로 추가된다

트라이는 문자열 처리에 있어 매우 빠르지만,

공간 복잡도 측면에서는 비용이 크므로 실전에서는 상황에 따라 해시맵, 셋 등과 비교하여 사용해야 한다

 

코드 리뷰

class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드들
        self.is_end = 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 = True

    # 문자열 존재 여부 확인 (Fetch)
    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

    # 접두사 검색
    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    # 문자열 삭제 (Delete)
    def delete(self, word):
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end:
                    return False  # 존재하지 않는 단어
                node.is_end = 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 not node.is_end and len(node.children) == 0
            return False

        _delete(self.root, word, 0)

# 트라이 사용해보기
trie = Trie()

# 단어 삽입
trie.insert("apple")
trie.insert("app")
trie.insert("bat")

# 검색 테스트
print(trie.search("app"))     # True
print(trie.search("apple"))   # True
print(trie.search("bat"))     # True
print(trie.search("batman"))  # False

# 삭제 후 검색
trie.delete("app")
print(trie.search("app"))     # False
print(trie.search("apple"))   # True (apple은 남아있음)

trie.delete("apple")
print(trie.search("apple"))   # False

단어 삽입 순서

• 노드를 루트로 초기화
  문자의 수만큼 반복:
  • 현재 문자가 자식에 없으면 새 노드 생성
  • 노드를 자식으로 이동
• 마지막 노드에 is_end = True 표시

return node.is_end 는 단순히 “경로가 존재한다”가 아니라
“정확히 이 단어가 삽입되어 있는가?” 를 판별하는 핵심이다

startsWith()는 트라이에 존재하는 어떤 단어의 앞부분과 일치하는지를 확인하는 함수
단어가 끝났는지 아닌지는 중요하지 않다

 

시간 복잡도

연산	시간 복잡도	설명
삽입 (Insert)	O(|S|)	문자열 S의 각 문자를 따라가며 노드를 생성
탐색 (Search / Fetch)	O(|S|)	한 문자씩 내려가며 존재 여부 확인
삭제 (Delete)	O(|S|)	리프까지 내려가며 end flag 제거, 필요 시 노드 삭제
접두사 검색 (StartsWith)	O(|P|)	문자열 P의 길이만큼만 탐색

|S|는 입력 문자열의 길이
|P|는 접두사(prefix)의 길이