토픽 60 / 82

Trie (트라이, 접두사 트리)

문자열 집합을 저장하는 트리 자료구조로 각 노드가 문자를 나타내며 루트에서 노드까지의 경로가 접두사를 형성하여 O(m) 시간에 검색, 삽입, 삭제 가능 (m=문자열 길이)

목적: 빠른 문자열 검색, 접두사 검색, 자동 완성, 사전 구현

특징: 트리 구조, 공통 접두사 공유, O(m) 연산, 공간 트레이드오프

구조: 루트=빈 문자열, 간선=문자, 리프 또는 종료 표시=완전한 단어

삽입: 루트부터 문자열을 따라 이동, 없는 노드 생성, 마지막에 종료 표시, O(m)

검색: 루트부터 문자열을 따라 이동, 모든 문자 존재하고 종료 표시 있으면 존재, O(m)

삭제: 검색 후 종료 표시 제거, 자식 없는 노드 역순 삭제, O(m)

접두사 검색: 접두사까지 이동, 하위 모든 단어 수집, 자동 완성

시간 복잡도: 삽입/검색/삭제 O(m), m=문자열 길이

공간 복잡도: O(총 문자 수), 최악 O(ALPHABET_SIZE × n × m)

장점: 빠른 검색(O(m)), 접두사 검색 효율, 자동 완성, 사전순 순회

단점: 메모리 많음, 포인터 오버헤드, 희소 노드

최적화: Compressed Trie(Patricia Trie), Ternary Search Tree, Hash Map 대신 배열

적용사례: 자동 완성, IP 라우팅(Longest Prefix Match), 맞춤법 검사, 사전, T9 입력

비교: Trie(O(m)/접두사) vs 해시(O(1)/접두사불가) vs BST(O(log n)/비교)

연관: 트리, 문자열, Aho-Corasick, Suffix Tree, 자동 완성