트라이 (Trie)

트라이 (Trie)

문자열 집합을 저장하는 트리 자료구조로, 각 노드가 문자 하나를 표현하고 루트부터 리프까지의 경로가 하나의 문자열을 형성하여 빠른 문자열 검색과 접두사 매칭을 지원

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

특징: 접두사 공유, 문자 단위 노드, 빠른 검색, 공간 트레이드오프

구성요소: ① 루트(빈 문자열) ② 노드(문자+자식 포인터) ③ 종료 플래그(isEndOfWord)

구조: 각 노드는 자식 포인터 배열(크기 = 알파벳 크기, 예: 26) 또는 해시맵

동작

• •삽입(Insert): 문자열 순회, 없는 노드 생성, 마지막 노드에 종료 플래그
• •검색(Search): 문자열 순회, 모든 문자 존재 + 종료 플래그 확인
• •접두사 검색(StartsWith): 문자열 순회, 모든 문자 존재 확인

시간 복잡도

• •삽입·검색·삭제: O(m) - m = 문자열 길이, 문자열 수(n)에 독립적
• •접두사 매칭: O(m)

공간 복잡도: O(ALPHABET_SIZE × n × m) - 최악, 실제는 접두사 공유로 절약

장점: 빠른 검색(O(m)), 접두사 매칭, 자동완성, 정렬된 순회, 문자열 수에 독립적

단점: 메모리 사용 많음(포인터 배열), 희소 트리, 구현 복잡도

최적화: 압축 트라이(Compressed Trie/Radix Tree), 해시맵 자식(메모리 절약)

적용사례: 자동완성, 검색 엔진, 사전, IP 라우팅, 문자열 매칭, 철자 검사

비교: 트라이(O(m)/접두사) vs 해시(O(m)/정확매칭) vs BST(O(m log n))

연관: Radix Tree, 접두사 트리, 문자열 알고리즘, 자동완성