알고리즘 - 6. Trie (접두사 트리)
Trie를 사용하는 시점
문자열 컬렉션에 대해 빠른 접두사 기반 연산이 필요할 때 Trie를 사용합니다. "Trie"라는 이름은 "retrieval"(검색)이라는 단어에서 유래했으며("try"처럼 발음), 1960년 Edward Fredkin이 고안했습니다. "retrieval"에서 파생되었지만, 특별히 빠른 문자열 검색과 접두사 매칭 연산을 위해 설계되었습니다.
대체 이름: Trie는 일반적으로 "접두사 트리(Prefix Tree)" 또는 **"디지털 트리(Digital Tree)"**라고도 불립니다. "접두사 트리"라는 이름이 특히 직관적인데, 트리의 모든 노드가 그 자손들의 공통 접두사를 나타내기 때문입니다. 일부 문헌에서는 "기수 트리(Radix Tree)"라고도 부르지만(엄밀히 말하면 Radix Tree는 Trie의 공간 최적화된 변형입니다).
가장 일반적으로 단어 검증에 사용되지만, 다음과 같은 용도에도 뛰어납니다:
- 자동완성/추천(전형적인 사용 사례 - 공통 접두사를 가진 모든 단어 찾기)
- 맞춤법 검사기(단어가 사전에 존재하는지 확인)
- IP 라우팅 테이블(최장 접두사 매칭)
- 전화번호부(접두사로 연락처 검색)
- 단어 게임(스크래블에서 단어 검증, 보글에서 단어 찾기)
- 다수의 문자열에 대한 효율적인 접두사 매칭이나 존재 확인이 필요한 모든 문제
예제 문제
자동완성 시스템: 단어 사전 ["apple", "app", "apricot", "application", "apply", "banana", "band", "bandana"]가 주어졌을 때, 다음 기능을 갖춘 검색 시스템을 구현하세요:
- "apple"이 유효한 단어인지 빠르게 확인할 수 있다
- 자동완성을 위해 "app"으로 시작하는 모든 단어를 찾을 수 있다
- 사전에 새로운 단어를 효율적으로 추가할 수 있다
답변: Trie는 세 가지 연산 모두를 O(m) 시간에 처리합니다. 여기서 m은 단어/접두사의 길이이며, 사전 크기와 무관합니다!
Trie가 사전을 저장하는 방법
다음은 예제 단어들이 Trie 구조를 형성하는 모습입니다:
root
/ \
a b
/ |
p a
/|\ |\
p r i n d
| | | | |
l i c a a
| | | | |
[e*] c a [n*] n
| | |
o t [a*]
| |
[t*] i
|
o
|
[n*]
[*] = 단어 종료 마커
단어: app*, apple*, apricot*, application*, apply*, banana*, band*, bandana*"app", "apple", "application", "apply"가 모두 접두사 "app"을 공유하며, 이것이 단 한 번만 저장되는 것에 주목하세요!
가장 중요한 통찰
Trie는 공간을 속도와 맞바꿔 공통 접두사를 공유합니다 - 루트에서 노드까지의 각 경로가 접두사를 나타내므로, 저장된 문자열의 수와 무관하게 O(m) 연산이 가능합니다. 검색하는 문자만 순회하기 때문입니다.
기억할 점: Trie의 천재성은 문자열 연산을 트리 순회로 변환하는 데 있습니다. 전체 문자열을 반복적으로 비교하는 대신, 문자 하나씩 단일 경로를 따라갑니다. 각 노드에서의 결정은 단순히 "이 문자가 자식으로 존재하는가?"입니다. 이 단순한 순회가 모든 공유 접두사를 자동으로 활용합니다.
왜 "Tree"가 아니라 "Trie"인가: 트리 구조이지만, "Trie"라는 이름은 접두사 공유를 통한 효율적인 문자열 재trieval(검색)이라는 특수한 목적을 강조하여 일반 트리와 구별합니다. 단순히 계층적 데이터를 위한 트리가 아니라, 문자열 연산에 특화되어 최적화된 트리입니다.
의사결정 프레임워크
보편적인 Trie 의사결정
모든 Trie 연산은 하나의 질문으로 귀결됩니다:
"현재 노드가 이 문자에 대한 자식을 가지고 있는가?"
- 예 → 그 경로를 따라간다
- 아니오 → 생성한다(삽입) 또는 결과를 반환한다(검색/접두사)
이 단일 결정을 각 문자에 대해 반복함으로써 모든 Trie 연산이 작동합니다.
연산의 각 문자에서 이 결정에 직면합니다:
- 삽입 시: 새 노드를 생성할까, 기존 경로를 따라갈까?
- 검색 시: 기존 경로를 따라 내려갈까, false를 반환할까?
- 접두사 매칭 시: 경로가 존재하는 동안 계속 따라간다
코드
설계 선택 설명
function createTrieNode() {
return {
isEndOfWord: false, // Why: 완전한 단어와 접두사를 구분
children: new Map(), // Why: Map은 희소 문자 집합을 효율적으로 처리
}; // (사용하지 않는 문자를 위해 메모리를 낭비하는 array[26]과 비교)
}핵심 Trie 구현
function Trie() {
const root = createTrieNode();
function insert(word) {
let currentNode = root;
for (const char of word) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Create new path or follow existing?
if (!hasChildWithChar) {
const newNode = createTrieNode();
currentNode.children.set(char, newNode);
}
currentNode = currentNode.children.get(char);
}
// Mark the end of a complete word
currentNode.isEndOfWord = true;
}
function search(word) {
let currentNode = root;
for (const char of word) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Path exists or return false?
if (!hasChildWithChar) {
return false; // Character not found, word doesn't exist
}
currentNode = currentNode.children.get(char);
}
// Found all characters, but is it a complete word?
const isCompleteWord = currentNode.isEndOfWord;
return isCompleteWord;
}
function startsWith(prefix) {
let currentNode = root;
for (const char of prefix) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Continue traversal or prefix not found?
if (!hasChildWithChar) {
return false;
}
currentNode = currentNode.children.get(char);
}
// If we've traversed the entire prefix, it exists
return true;
}
// Return the public interface
return {
insert,
search,
startsWith,
};
}
// Example usage with our dictionary
const dictionary = Trie();
const words = ["apple", "app", "apricot", "application", "apply"];
for (const word of words) {
dictionary.insert(word);
}
console.log(dictionary.search("apple")); // true
console.log(dictionary.search("app")); // true
console.log(dictionary.search("appl")); // false (not a complete word)
console.log(dictionary.startsWith("app")); // true단계별: "app" 삽입
빈 Trie에 단어 "app"을 삽입하는 과정을 추적해봅시다:
시작 상태: root (비어있음)
1. 'a' 처리:
- root가 자식 'a'를 가지고 있는가? 아니오
- 'a'에 대한 새 노드 생성
- 노드 'a'로 이동
상태: root → a
2. 'p' 처리:
- 'a'가 자식 'p'를 가지고 있는가? 아니오
- 'p'에 대한 새 노드 생성
- 첫 번째 'p'로 이동
상태: root → a → p
3. 'p' 처리:
- 첫 번째 'p'가 자식 'p'를 가지고 있는가? 아니오
- 두 번째 'p'에 대한 새 노드 생성
- 두 번째 'p'로 이동
상태: root → a → p → p
4. 단어 종료 표시:
- 두 번째 'p'에 isEndOfWord = true 설정
최종: root → a → p → p[*]고급 연산
접두사를 가진 모든 단어 찾기(자동완성)
// Add this to the Trie function's returned object
function findAllWordsWithPrefix(prefix) {
let currentNode = root;
// First, navigate to the prefix end
for (const char of prefix) {
const hasChildWithChar = currentNode.children.has(char);
if (!hasChildWithChar) {
return []; // Prefix doesn't exist
}
currentNode = currentNode.children.get(char);
}
// Collect all words starting from this node
const results = [];
collectWords(currentNode, prefix, results);
return results;
}
function collectWords(node, currentWord, results) {
const isWord = node.isEndOfWord;
if (isWord) {
results.push(currentWord);
}
// Recursively collect from all children
for (const [char, childNode] of node.children) {
const nextWord = currentWord + char;
collectWords(childNode, nextWord, results);
}
}
// Usage example:
console.log(dictionary.findAllWordsWithPrefix("app"));
// Returns: ["app", "apple", "application", "apply"]흔한 구현 함정
-
단어 종료 마커를 잊어버림:
isEndOfWord가 없으면, "app"(완전한 단어)와 "appl"("apple"에 존재하는 접두사)을 구분할 수 없습니다 -
Map 대신 Array 사용:
- Array 방식:
children = new Array(26)은 몇 개의 문자만 사용할 때 메모리를 낭비합니다 - Map 방식:
children = new Map()은 실제로 존재하는 문자만 저장합니다
- Array 방식:
-
빈 문자열을 처리하지 않음: 빈 문자열이 Trie에서 유효한 단어인지 미리 결정합니다. 대부분의 구현은 무효로 처리합니다
-
접두사 존재와 단어 존재를 혼동: 우리 Trie에서 "appl"은 접두사로 존재합니다("apple"로의 경로), 하지만 그 자체로는 단어가 아닙니다
의문 해소
흔한 의문: "Trie가 과도하게 메모리를 사용하지 않을까요? 'a', 'ab', 'abc', ..., 'abcdefghijklmnopqrstuvwxyz' 같은 단어가 있으면, 단 하나의 단어를 위해 26개의 노드를 생성하게 되잖아요!"
시각적 비교: Trie vs 원시 문자열 저장
"algorithm", "algorithms", "algorithmic", "algorithmically" 저장을 분석해봅시다:
Trie 없이(원시 문자열 저장):
- "algorithm" → 9문자
- "algorithms" → 10문자
- "algorithmic" → 11문자
- "algorithmically" → 16문자
합계: 46개의 문자 저장 단위
Trie 사용(접두사 공유):
a-l-g-o-r-i-t-h-m (9노드)
├─ [end] (단어: "algorithm")
├─ s-[end] (1노드, "algorithms"용)
└─ i-c (2노드)
├─ [end] (단어: "algorithmic")
└─ a-l-l-y-[end] (4노드, "algorithmically"용)
합계: 16노드 (9 + 1 + 2 + 4)접두사 공유의 핵심 통찰
마법: 46문자 대신, "algorithm"이 네 단어 모두에서 공유되므로 단 16개의 노드만 필요합니다!
실제 효율성 - 영어 단어 사전을 생각해봅시다:
- 단어들이 큰 접두사를 공유합니다("run", "running", "runner", "runs")
- 공통 패턴이 나타납니다("pre-", "un-", "re-", "-ing", "-ed")
- 단어를 더 추가할수록 접두사 공유가 더 많이 발생합니다
"pre-"로 시작하는 1000개 단어의 예:
- 순진한 저장: 약 7000문자("pre" 뒤 평균 7문자)
- Trie 저장: "pre"에 3노드 + 분기 경로(7000보다 훨씬 적음)
Trie가 실제로 공간을 낭비하는 경우
Trie가 비효율적인 경우:
- 공통 접두사가 없음: ["xyz", "abc", "qrs"] 저장은 완전히 별개의 경로를 생성
- 매우 짧은 문자열: 노드 구조의 오버헤드가 문자열 길이를 초과
- 무작위 데이터: UUID나 해시는 의미 있는 접두사 패턴이 없음
공간-시간 트레이드오프
Trie의 탁월함: 탁월한 시간 보장을 위해 공간을 희생합니다:
| 연산 | HashMap | Trie |
| ------------ | -------------------------- | ----------------------------------- |
| 삽입 | 평균 O(m), 최악 O(n×m) | 항상 O(m) |
| 검색 | 평균 O(m), 최악 O(n×m) | 항상 O(m) |
| 접두사 매칭 | O(n×m) - 모든 문자열 확인 | O(m) - 경로만 따라감 |
| 자동완성 | O(n×m) - 모든 것 스캔 | O(m+k) - 접두사에 m, 결과에 k |
n = 문자열 개수, m = 문자열 길이, k = 결과 개수보장: Trie는 무작위 문자열에 대해 더 많은 메모리를 사용할 수 있지만, 접두사 연산에 대해 최고의 시간복잡도를 제공합니다. 자연스러운 접두사 패턴(단어, URL, 파일 경로)을 가진 영역에서는 시간과 공간 모두에서 효율적입니다!