에듀테크 프로젝트 대시보드
트라이 (Trie) — 접두사 트리
트라이는 문자열을 한 글자씩 간선(edge)에 나눠 담는 트리다.
뿌리(root)에서 어떤 노드까지 내려가며 읽은 글자들이 곧 접두사(prefix)가 된다.
그래서 "ca 로 시작하는 단어 모두" 같은 질문에 아주 빠르게 답할 수 있어
검색창 자동완성, 사전, IP 라우팅 테이블 등에 쓰인다.
이름은 retrieval(검색)에서 왔고, 보통 "트라이"라고 읽는다.
초록 노드 = 여기서 끝나는 단어가 있음(end-of-word) · 주황 경로 = 지금 검색 중인 접두사 · 회색 = 접두사 경유 노드
P에만 비례 → 사전 크기와 무관.| 연산 | 트라이 (Trie) | 해시맵 (Hash) | 정렬 배열 / BST |
|---|---|---|---|
| 정확히 일치 검색 | O(L) · 해시 계산 불필요 |
O(L) 평균 (해시 + 충돌) |
O(L·log N) |
| 접두사로 시작하는 모든 단어 |
O(P + k)(P=접두사, k=결과 수) |
전체 스캔 O(N·L) |
O(log N + k)(범위 이분탐색) |
| 정렬된 순서로 순회 | 자식을 사전순 방문 → 공짜 | 불가 (별도 정렬) | 이미 정렬됨 |
| 메모리 | 노드마다 자식 포인터 배열 → 큼 (공통 접두사는 공유해 절약) |
보통 가장 작음 | 작음 |
핵심: 해시맵은 "이 단어 있어?"엔 최고지만 "이 접두사로 시작하는 것 전부"엔 무력하다. 트라이는 공통 접두사를 물리적으로 공유하기 때문에 그 질문에 자연스럽게 강하다. 메모리가 부담되면 자식을 배열 대신 맵으로 두거나, 외자식 체인을 압축한 Radix Tree(Patricia trie)를 쓴다 — 리눅스 커널 라우팅, DB 인덱스가 이 방식.
class Trie: def __init__(self): self.children = {} # 글자 -> Trie 노드 self.is_end = False # 여기서 끝나는 단어가 있는가 def insert(self, word): node = self for ch in word: node = node.children.setdefault(ch, Trie()) # 없으면 생성 node.is_end = True def _walk(self, prefix): # 접두사 경로 끝 노드 반환 (없으면 None) node = self for ch in prefix: if ch not in node.children: return None node = node.children[ch] return node def search(self, word): node = self._walk(word) return node is not None and node.is_end def autocomplete(self, prefix, limit=10): node = self._walk(prefix) if node is None: return [] out = [] def dfs(n, path): if len(out) >= limit: return if n.is_end: out.append(prefix + path) for ch in sorted(n.children): # 사전순 dfs(n.children[ch], path + ch) dfs(node, "") return out # t = Trie(); [t.insert(w) for w in ("car","card","care","cat","dog")] # t.autocomplete("ca") -> ['car', 'card', 'care', 'cat']