Trie (prefix tree) 는 문자열을 글자 단위로 쪼개 트리에 저장하는 자료구조다. 루트에서 시작해 글자를 하나씩 따라 내려가면 단어가 된다. 공통 접두사를 가진 단어들은 그 접두사까지 같은 경로를 공유한다.
"app", "apple", "apt" 를 넣은 모습
(root)
└─ a
└─ p
├─ p ● (app 끝)
│ └─ l
│ └─ e ● (apple 끝)
└─ t ● (apt 끝)
연결 리스트처럼 보이지만 노드마다 다음 글자가 여러 개일 수 있으므로 트리다. 그래서 next 포인터 하나 대신 “글자 → 자식 노드” dict 를 둔다.
노드에 필요한 것
children: 글자를 키로, 자식 노드를 값으로 갖는 dictis_end: 여기서 끝나는 단어가 있는지. 이것이 없으면"app"을 넣었는지,"apple"의 앞부분일 뿐인지 구분할 수 없다.
글자 자체를 노드에 저장할 필요는 없다. 이미 부모 dict 의 키로 들어 있다.
구현
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _find(self, prefix: str):
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not Nonesearch 와 startsWith 는 글자를 따라 내려가는 과정이 같고, 마지막에 is_end 를 확인하는지만 다르다. 그래서 내려가는 부분을 _find 로 뺀다.
자주 하는 실수
- 노드 하나를 객체 두 개로 표현하기. 자식 dict 를 담는 클래스와
is_end를 담는 클래스를 따로 두면curr[w].node.is_end,curr[w].trie처럼 접근이 길어진다. 노드 클래스 하나에children과is_end를 함께 둔다. - 현재 위치를 dict 로 들고 다니기.
curr가 노드가 아니라 자식 dict 를 가리키면, 마지막 글자에is_end를 표시하려고 인덱스를 비교해야 하고, 접두사 노드에서 탐색을 시작하는 확장 (아래 E) 도 번거로워진다.curr는 노드를 가리키게 하고, 루프가 끝난 뒤node.is_end = True한 줄로 표시한다.
복잡도와 해시셋과의 차이
단어 길이를 이라 하면 insert, search, startsWith 모두 이다. 저장된 단어가 몇 개든 상관없다.
단어 존재 여부만 확인한다면 해시셋도 평균 이다 (문자열 해시 계산에 길이만큼 걸린다). Trie 의 장점은 접두사로 찾기다. 해시셋으로 “ap 로 시작하는 단어가 있나?” 를 물으려면 모든 단어를 훑어야 한다.
자동완성으로 확장하기
LeetCode 1268. Search Suggestions System 처럼 접두사로 시작하는 단어를 모으려면, _find 로 접두사 노드까지 내려간 뒤 거기서 DFS 로 is_end 인 노드를 모은다. 자식을 글자 순서대로 방문하면 사전순으로 나온다. 검색창 자동완성은 사전순 대신 검색 빈도 같은 점수로 후보를 정렬한다 (Query Auto-Completion).
def suggest(self, prefix: str, limit: int = 3) -> list[str]:
node = self._find(prefix)
result = []
def dfs(n, path):
if len(result) == limit:
return
if n.is_end:
result.append(path)
for ch in sorted(n.children):
dfs(n.children[ch], path + ch)
if node:
dfs(node, prefix)
return result