트라이는 문자열을 효율적으로 저장하고 검색하기 위한 자료구조이다. 주로 문자열 처리와 관련된 문제를 해결하는데 유용하다.
- 자동완성, 사전(Dictionary) 구현, 검색 추천 등에서 많이 사용된다.
특징
- 노드 구조
- 트리는 루트부터 시작하며, 각 노드는 문자(char)와 연결된다.
- 노드에는 해당 문자로 끝나는 단어의 여부를 나타내는 플래그(종료 마커)도 포함 될 수 있다.
- 계층적 구조
- 각 경로는 문자열의 접두사를 표현한다. 예를 들어, "cat"과 "car"가 저장된 트라이에서는 "ca"가 공통 접두사로 저장된다.
- 공간 효율성
- 공통 접두사를 공유하기 때문에 유사한 문자열이 많을 경우 메모리 사용을 줄일 수 있다.
- 하지만, 노드의 갯수가 많아지면 공간을 더 차지하게 된다.
- 시간 복잡도
- 검색, 삽입, 삭제, 모두 문자열의 길이를 기준으로 한다. O(Length)
이진 트리와의 차이점?
| Trie | 이진 트리 |
| 문자열을 저장하고 검색하는 데 최적화 된 구조이다. | 숫자나 데이터 저장에 주로 사용된다. |
| 각 노드는 여러 자식을 가질 수 있다. | 각 노드는 최대 두 개의 자식을 가질 수 있다. |
| 문자열의 접두사를 기반으로 데이터 구조를 생성한다. | 데이터를 정렬하여 탐색 속도를 높일 수 있다. |
| 검색 시간 복잡도는 문자열 길이에 비례한다. (O(Length)) | 일반적인 검색 시간 복잡도는 O(log n)이다. |
| 공통 접두사를 공유해서 공간을 절약 할 수 있다. | 공간 절약보다는 간단하고 일반적인 자료구조로써 사용한다. |
구조적 원리
트리의 계층적 표현
Trie는 트리의 형태로 데이터를 표현하는데, 각 문제를 노드로 저장한다. 루트에서 시작해 문자열의 첫 번째 문자부터 차례대로 각 문자를 노드로 연결한다. 예를 들어, 아래와 같이 저장 된다.
- apple : root - a - p - p - l - e
- app : root - a - p - p (apple과 접두사를 공유하게 된다.)
이처럼 공통된 접두사는 동일한 경로를 공유하므로, 데이터 중복을 방지 할 수 있다.
Trie의 핵심 기능
- 삽입 (Insert)
- 새로운 문자열을 삽입 할 때, 루트에서 시작하여 각 문자를 노드로 연결한다. 이미 존재하는 문자는 재사용하며, 문자열의 끝 지점에서 "단어 종료 표시" 플래그를 설정한다.
- 검색 (Search)
- 입력된 문자열을 트리를 탐색하면서 한 문자씩 경로를 따라간다. 모든 문자가 연결 되어있는지 확인 한 뒤, 마지막 노드의 "단어 종료 표시" 여부를 확인한다.
- 접두사 탐색 (Starts With)
- 특정 접두사로 시작하는 모든 문자열을 빠르게 탐색 할 수 있다. 이는 루트에서 접두사에 해당하는 경로를 따라간 후, 그 하위 노드들을 탐색하는 방식으로 작동한다.
예시
cat | car | cart | dog | door 를 저장하겠다고 가정해보자.
| Root ├── c │ └── a │ ├── t (단어 종료) │ └── r │ └── t (단어 종료) └── d └── o ├── g (단어 종료) └── o └── r (단어 종료) |
"ca" 접두사는 cat, car이 공유하며, "do" 접두사는 "dog", "door"가 공유한다.
텍스트 기반 애플리케이션에서 그 잠재력을 발휘 할 수 있는 자료구조이다.