정의

트라이(Trie)는 문자열을 저장하고 효율적으로 검색하기 위한 트리 자료구조입니다. 각 노드는 문자 하나를 나타내며, 루트에서 특정 노드까지의 경로가 하나의 문자열(또는 접두사)을 형성합니다.

핵심 특성

• ✓삽입, 검색, 삭제 모두 O(m) 시간복잡도 (m = 문자열 길이)
• ✓접두사 검색에 매우 효율적 (자동완성, 사전 구현에 활용)
• ✓공통 접두사를 공유하여 메모리 효율적
• ✓알파벳 크기에 따라 메모리 사용량 증가 가능

시간 복잡도