Trie : 트라이

Trie : 트라이

빠른 패턴 매칭을 지원하기 위해 문자열들을 저장하는 트리 기반의 자료구조이다.

< Trie의 예시 >

Trie의 특징

1. Trie의 주요 질의 연산은 패턴 매칭과 접두사 매칭(prefix matching)이다.
2. Trie는 루트로부터 리프 노드들까지의 경로로써 문자열을 표현한다.

크기 d의 알파벳으로 s개의 문자열의 집합 S(전체 길이 n)를 저장하는 Trie

- Trie의 모든 내부 노드는 최대 d개의 자식을 가진다.
- Trie는 s개의 리프 노드들을 가진다.
- Trie의 높이는 S에서 가장 긴 문자열의 길이와 같다.
- Trie의 노드들의 개수는 O(n)이다.
- 크기가 m인 문자열에 대한 탐색 실행시간은 O(dm)이다.

Trie의 단점

Trie는 각 노드마다 실제로 다음에 올 문자가 없더라고 다음 문자를 가리킬 포인터가 필요하다. 
이러한 점 때문에 공간 복잡도에서 단점을 갖는다.

Trie 사용 예시

- 예측 문자, 자동 완성
- 맞춤법 검사
- 근사 일치 알고리즘
- 전문 검색