트라이 (Trie)
문자열을 문자 하나씩 트리의 간선에 담아, 공통 접두사를 한 경로로 공유하는 자료구조
왜 필요한가
"자바"로 시작하는 단어를 모두 찾는 작업을 생각해봅시다.
| 방법 | 시간 | 문제 |
|---|---|---|
| 전체 순회하며 비교 | 단어 수에 비례 | 단어가 100만 개면 100만 번 비교 |
| 정렬 후 이진 탐색 | 로그 시간 | 접두사 범위를 찾을 수 있지만 삽입이 비싸다 |
| 해시 테이블 | 상수 시간 | 정확히 일치하는 것만 찾는다. 접두사 검색 불가 |
| 트라이 | 접두사 길이에 비례 | 단어가 몇 개든 "자바" 3글자만 따라가면 된다 |
마지막 줄이 핵심입니다. 저장된 단어 수와 무관하게 찾는 문자열의 길이만큼만 내려갑니다.
구조
"cat", "car", "card" 를 담으면 이렇게 됩니다.
(root)
|
c
|
a
/ \
t r
(끝) |\
(끝) d
(끝)
"car" 와 "card" 가 c-a-r 경로를 공유합니다. 공통 접두사가 길수록 메모리를 아낍니다.
연산
| 연산 | 시간 | 설명 |
|---|---|---|
| 삽입 | 문자열 길이에 비례 | 문자마다 한 칸 내려간다 |
| 검색 | 문자열 길이에 비례 | 같다 |
| 접두사 검색 | 접두사 길이 + 결과 수 | 그 아래를 모두 모은다 |
| 삭제 | 문자열 길이에 비례 | 자식이 없는 노드를 지우며 올라온다 |
해시 테이블도 검색이 문자열 길이에 비례합니다(해시를 계산해야 하므로). 트라이의 고유한 값은 접두사 검색과 정렬 순서입니다.
쓰이는 곳
| 용도 | 이유 |
|---|---|
| 검색어 자동완성 | 입력 중인 접두사로 후보를 찾는다 |
| 사전과 맞춤법 검사 | 존재 여부와 비슷한 단어 찾기 |
| IP 라우팅 테이블 | 가장 긴 접두사 일치 |
| 금칙어 필터 | 여러 단어를 한 번에 훑는다 |
한계
메모리를 많이 씁니다. 노드마다 자식 포인터 배열을 두면 알파벳 26개짜리 배열이 노드마다 생깁니다. 실무에서는 이렇게 줄입니다.
| 방법 | 내용 |
|---|---|
| 해시맵으로 자식 관리 | 있는 자식만 담는다 |
| 압축 트라이 | 자식이 하나뿐인 경로를 하나의 노드로 합친다 |
| 이중 배열 트라이 | 배열 두 개로 표현해 메모리를 크게 줄인다 |