LLD Data Structures in Design Context: Trie — A Data Structure Designed for Prefix Search

개요

Trie는 일반적인 단어 저장 방식이 아니라, 동일한 접두사를 공유하는 모든 항목을 효율적으로 찾는 데 특화된 트리 형태의 자료구조입니다.

주요 내용

* Trie는 각 노드가 문자를 나타내며, 동일한 접두사로 시작하는 단어들은 동일한 경로를 공유합니다.
* "car", "card", "care", "cart"와 같은 단어들은 "car"라는 접두사를 공유하며, Trie에서는 이 공통된 경로가 한 번만 저장됩니다.
* HashMap은 정확한 값 조회를, Heap은 우선순위 높은 항목 조회를, Queue는 다음 작업 순서를, Stack은 현재 작업 컨텍스트를 묻는 반면, Trie는 "무엇이 이 문자로 시작하는가?"라는 질문에 답합니다.
* 단어를 Trie에 삽입할 때는 해당 문자로 구성된 경로를 따라가며, 이미 존재하는 경로는 재사용합니다.
* 사용자가 입력한 접두사에 따라 Trie는 해당 경로를 따라가고, 그 경로 아래에 있는 모든 단어를 검색 결과로 제시하여 효율적인 검색을 지원합니다.
* Trie를 활용하면 자동 완성이나 실시간 검색과 같은 기능에서 서비스 전체가 반복적인 데이터 스캔을 수행하는 대신, 전용 검색 컴포넌트가 효율적인 접두사 검색을 담당하도록 설계할 수 있습니다.
* 일반적인 실수로는 Trie를 단순한 트리로 여기거나, 정확한 조회에만 사용하거나, 접두사 공유의 이점을 간과하거나, 검색 로직과 비즈니스 로직을 혼합하는 경우가 있습니다.
* 엔지니어링 관점에서 Trie는 사용자가 부분 값을 입력하고, 입력 중 제안이 나타나며, 많은 저장 값이 공통 접두사를 공유하고, 접두사 검색이 핵심 기능일 때 자연스러운 선택지가 됩니다.

시사점

Trie는 사용자의 입력에 따라 검색 범위를 좁혀나가며 빠르고 반응성 좋은 검색 경험을 제공하는 데 핵심적인 역할을 수행합니다.