구글이나 네이버 검색창에 '자료'라고만 쳐도 '자료구조', '자료구조 알고리즘'이 밑에 자동으로 추천되는 원리가 궁금하신가요?
이러한 마법 같은 문자열 검색 및 자동완성에 특화된 자료구조가 바로 트라이(Trie)입니다. 트라이는 단어의 철자(알파벳 등) 하나하나를 노드로 쪼개어 트리 형태로 연결한 '접두사 트리(Prefix Tree)' 구조를 띕니다. 덕분에 문자열의 길이에만 비례하는 압도적인 검색 속도를 자랑합니다.
1. 트라이(Trie)의 구조와 원리
2. 트라이의 강력한 장점과 치명적인 단점
구분
내용
비고
강력한 장점 (속도)
문자열의 최대 길이가 M일 때, 탐색 시간 복잡도는 무조건 O(M)입니다. 내부에 저장된 데이터(단어)가 1억 개라도 속도는 단어의 길이에만 좌우됩니다.
일반적인 문자열 검색 시 O(N * M)에 비해 압도적
치명적인 단점 (메모리)
모든 글자(알파벳 26자)마다 포인터 배열이나 해시맵 노드를 가져야 하므로 메모리 낭비가 매우 극심합니다.
최적화를 위해 메모리를 덜 쓰는 Radix Tree나 Ternary Search Tree를 대체제로 쓰기도 함
💡 실무 지식: 검색어 자동완성은 트라이로만 만드나요?
알고리즘 인터뷰나 소규모 프로젝트에서는 트라이(Trie)가 자동완성의 정석입니다. 하지만 구글이나 쿠팡 같은 실제 대규모 환경에서는 트라이 하나만 쓰지 않습니다.
주로 ElasticSearch(엘라스틱서치)라는 검색 엔진을 활용해 Edge N-gram(글자를 쪼개어 인덱싱) 방식으로 구현하거나, 인기 검색어는 Redis의 Sorted Set을 사용해 캐싱하여 초고속으로 뿌려주는 방식을 훨씬 더 많이 사용합니다.
// 📂 Trie.js (JavaScript)
// 트라이 노드 클래스: 자식 노드들을 담는 객체와 단어의 끝임을 알리는 플래그를 가집니다.
class TrieNode {
constructor() {
this.children = {}; // 알파벳을 키로 하는 자식 노드들
this.isEndOfWord = false; // 단어의 끝(단어 완성) 여부
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// 🌟 단어 삽입 (Insert)
insert(word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let char = word[i];
if (!current.children[char]) {
current.children[char] = new TrieNode(); // 없으면 새로운 노드 생성
}
current = current.children[char]; // 다음 노드로 이동
}
current.isEndOfWord = true; // 마지막 글자 노드에 단어 끝 표시
}
// 🌟 단어 완전 일치 검색 (Search)
search(word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let char = word[i];
if (!current.children[char]) return false; // 도중에 길이 끊기면 없음
current = current.children[char];
}
return current.isEndOfWord; // 마지막 글자까지 도달했고, 단어의 끝이라면 true
}
// 🌟 접두사(Prefix) 검색 (자동완성에 주로 사용됨)
startsWith(prefix) {
let current = this.root;
for (let i = 0; i < prefix.length; i++) {
let char = prefix[i];
if (!current.children[char]) return false;
current = current.children[char];
}
return true; // 접두사까지만 무사히 도달하면 true
}
}
// 🌐 테스트 실행
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log("apple 검색:", trie.search("apple")); // true
console.log("app 검색:", trie.search("app")); // true
console.log("appl 검색:", trie.search("appl")); // false (appl이라는 단어는 등록 안 됨)
console.log("app로 시작하는가?:", trie.startsWith("app")); // true
