Trie는 문자열 탐색을 빠르게 수행할 수 있도록 설계된 트리 기반 자료구조
- 특히 문자열 집합을 효율적으로 저장하고 검색하는 데 유용
- 특히 문자열의 접두사(prefix)를 빠르게 처리할 수 있는 구조라서 자동 완성, 사전(dictionary), 검색 엔진 등에 많이 쓰임
- K진 트리(K-ary tree)의 구조를 띔
- 찾고자 하는 문자열을 공간을 많이 사용하는 대신, 그 문자열의 길이의 속도만큼 초고속 탐색이 가능
- 주로 자동완성, 접두어 검색, 사전(dictionary) 구현에 사용됨
기본 구조
- 각 노드는 문자열의 문자 하나를 나타냄
- 루트 노드는 항상 비어 있음
- 루트 노드의 자식 노드는 각 단어들의 첫 글자
- 하나의 경로는 하나의 단어를 나타냄
- 문자열을 넣을수록 공통 접두사는 공유됨 → 메모리 절약
- 삽입, 검색의 시간복잡도는 문자열 길이
L에 대해 O(L) - 문자열의 끝은 isEnd 또는 isTerminal 플래그로 표시
Trie에 들어있는 문자열:
apple, april
bus, busy, beer, best
주요 연산
1. 삽입 (Insert)
- 한 글자씩 내려가며 경로가 없으면 노드를 새로 만듦
- 문자열의 각 문자를 순서대로 따라가며 노드 생성
- 중간에 이미 존재하는 문자가 있으면 재사용
- 마지막 문자 노드에 끝 표시 (isEnd = true)
2. 검색 (Search)
- 루트에서 시작해 문자열의 각 문자를 차례로 따라간다
- 마지막 글자까지 도달했다면 단어가 존재
- 없으면 False, 끝까지 도달하고
isEnd == true면 True
3. 접두어 검색 (StartsWith)
- 자동완성 기능
- 입력된 문자열이 어떤 문자열의 접두어로 사용되었는지 탐색
- 끝에 도달하기만 하면 True (isEnd 검사 X)
구현 방법
# Trie에서 각 노드를 나타내는 클래스
class TrieNode:
def __init__(self):
self.children = {} # 자식 노드를 담을 딕셔너리 (key: 문자, value: TrieNode)
self.is_end = False # 하나의 단어가 끝나는 지점을 표시하는 플래그
# Trie 전체를 관리하는 클래스
class Trie:
def __init__(self):
self.root = TrieNode() # 루트 노드는 빈 노드로 시작 (문자 없음)
# 단어 삽입 함수
def insert(self, word):
node = self.root # 루트부터 시작해서 아래로 탐색
for ch in word: # 단어의 각 문자마다
if ch not in node.children:
node.children[ch] = TrieNode() # 해당 문자가 없으면 새 노드 생성
node = node.children[ch] # 다음 노드로 이동
node.is_end = True # 단어 끝에 도달했음을 표시
# 단어 전체가 Trie에 있는지 검색
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children: # 해당 문자가 없으면 False
return False
node = node.children[ch] # 다음 문자로 이동
return node.is_end # 마지막 노드가 단어의 끝인지 확인
# 주어진 prefix로 시작하는 단어가 존재하는지 확인
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: # 접두사 문자가 없으면 False
return False
node = node.children[ch] # 다음 문자로 이동
return True # 모든 접두사 문자를 순회했으면 True
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")
print(trie.search("car")) # True
print(trie.search("can")) # False
print(trie.starts_with("ca")) # True
print(trie.starts_with("do")) # True시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 삽입 | O(L) |
| 탐색 | O(L) |
| 접두어 탐색 | O(L) |
- L: 문자열의 길이
- 일반적인 HashMap 기반 탐색은 O(1) 기대 시간이지만, 충돌 시 성능 저하 가능
- Trie는 문자 길이에 따라 항상 일정한 탐색 속도 보장
장점과 단점
| 장점 | 단점 |
|---|---|
| 문자열 길이에 따라 일관된 탐색 속도 | 메모리 사용량 많음 |
| 접두어 검색, 자동완성 등 빠르게 구현 가능 | 각 노드마다 알파벳 수만큼 포인터 필요 |
| 해시 충돌 없음 | 문자열이 적거나 짧으면 비효율적 |
구현 시 주의할 점
- 공간 최적화를 위해 자식 노드를 배열(26개 등) 대신 해시맵으로 구현 가능
- 문자열이 많고, 길이가 짧으면 Trie가 더 효과적
- Trie는 탐색의 효율을 위해 메모리를 희생하는 구조이므로, 문제의 조건을 보고 선택적으로 사용
