트라이(Trie, Prefix Tree)는 문자열을 효율적으로 저장·검색하기 위한 트리 기반 자료구조다. 각 노드가 문자 하나를 나타내며, 공통 접두사를 공유해 메모리를 절약한다. 자동완성, 사전 검색, 라우팅 테이블에 활용된다.
구조
삽입: "app", "apple", "application", "apt"
root
│
a
│
p
/ \
p t
│
l
/ \
e i
│
c
│
a
│
t
│
i
│
o
│
n
구현
python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
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
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # True
print(trie.starts_with("app")) # True
시간 복잡도
| 연산 | 복잡도 |
|---|
| 삽입 | O(L) — L은 문자열 길이 |
| 검색 | O(L) |
| 접두사 검색 | O(L) |
활용 사례
- •검색 자동완성 (Google, Naver 검색창)
- •맞춤법 검사기
- •IP 라우팅 테이블 (최장 접두사 매칭)
- •단어 게임 (보글, 스크래블)
관련 개념
참고문헌
- •Sedgewick & Wayne. Algorithms, 4th Ed. — Section 5.2
