트라이
트라이 (Trie)
트라이(Trie)는 'retrieval'에서 유래한 이름으로, 문자열을 저장하고 검색하는 데 특화된 트리 형태의 자료구조입니다. '디지털 트리(Digital Tree)' 또는 '접두사 트리(Prefix Tree)'라고도 불리며, 특히 특정 접두사로 시작하는 문자열을 찾는 작업에 매우 효율적입니다.
🔡 트라이의 구조와 특징
- 구조 (Structure)
> * 루트 노드는 비어 있습니다. > * 각 노드는 자식 노드에 대한 포인터 배열(또는 맵)을 가집니다. 배열의 크기는 알파벳의 수(e.g., 26)가 될 수 있습니다. > * 각 노드는 단어의 끝을 나타내는 불리언(boolean) 플래그(`isEndOfWord`)를 가집니다. > * 트리의 각 간선(edge)은 하나의 문자를 나타내며, 루트에서 특정 노드까지의 경로는 하나의 문자열(접두사)을 형성합니다.
- 동작 원리 (How it works)
> * 삽입 (Insertion) : 문자열의 각 문자를 따라 트리 아래로 이동합니다. 해당 문자에 해당하는 자식 노드가 없으면 새로 생성하고, 마지막 문자 노드에 `isEndOfWord`를 true로 표시합니다. > * 검색 (Search) : 삽입과 유사하게 문자열을 따라 트리 아래로 이동합니다. 문자열의 끝에 도달했을 때, 해당 노드의 `isEndOfWord`가 true이면 단어가 존재하는 것입니다.
👍 트라이의 장점과 단점
- 장점 (Advantages)
> * 매우 빠른 검색 속도 : 문자열의 길이를 M이라고 할 때, 검색과 삽입이 O(M)의 시간 복잡도를 가집니다. 저장된 문자열의 총개수와 상관없이 오직 검색하려는 문자열의 길이에만 영향을 받습니다. > * 접두사 기반 검색에 최적화 : 특정 접두사로 시작하는 모든 문자열을 효율적으로 찾을 수 있습니다. > * 알파벳순 정렬 : 트리를 전위 순회(Pre-order traversal)하면 저장된 모든 문자열을 알파벳순으로 쉽게 얻을 수 있습니다.
- 단점 (Disadvantages)
> * 메모리 비효율성 : 각 노드가 모든 가능한 문자에 대한 포인터를 유지해야 하므로, 저장 공간의 낭비가 심할 수 있습니다. > * 구현의 복잡성 : 다른 자료구조에 비해 상대적으로 구현이 복잡할 수 있습니다.
💡 개발자 핵심 Point
- 트라이는 문자열 검색과 관련된 문제에서 강력한 성능을 발휘하는 자료구조입니다.
- 활용 사례
> * 검색 엔진의 자동 완성 (Autocomplete) : 사용자가 입력하는 접두사를 기반으로 추천 검색어를 제시합니다. > * 사전 검색 / 맞춤법 검사 (Spell Checker) : 사전에 있는 단어인지 빠르게 확인합니다. > * IP 라우팅 : 라우터가 가장 긴 접두사 일치(Longest Prefix Match)를 찾는 데 사용됩니다.
- 메모리 문제를 해결하기 위해 '터너리 서치 트리(Ternary Search Tree)'나, 자식 노드를 배열 대신 해시맵으로 구현하는 등의 변형된 트라이 구조를 사용할 수 있습니다.
