참조: https://rebro.kr/86
참조: https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4
참조: https://youseop.github.io/2020-11-09-BAEKJOON-14425_%EB%AC%B8%EC%9E%90%EC%97%B4%EC%A7%91%ED%95%A9/
트라이(Trie) 자료구조란
- 문자열의 집합을 표현하는 트리 자료구조이다.(래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 한다.)
- 원하는 문자열을 빠르게 탐색할 수 있는 자료구조이다.
- 검색어 자동완성, 사전에서 찾기, 문자열 검사 등의 상황에서 사용된다.
트라이(Trie) 작동 원리
"ab", "abc", "car"를 저장하는 예시
생성 및 추가
"abc"의 경우
- 첫번째 문자 "a"는 초기에 trie 자료구조 내에는 아무것도 추가되어있지 않으므로 Head의 자식 노드에 "a"를 추가해준다.
- "a"노드에도 현재 자식이 하나도 없으므로, "b"를 자식 노드인 "a"의 자식으로 추가해준다.
- "c"도 마찬가지로 "b"의 자식 노드로 추가해준다.
- "abc"라는 단어가 여기서 끝남을 알리기 위해 현재 노드에 "abc"라고 표시한다.
"ab"의 경우
- 현재 Head의 자식 노드로 "a"가 이미 존재하므로, 추가하지 않고 "a"노드로 이동한다.
- "b"도 "a"의 자식 노드로 이미 존재하기 때문에 "b"노드로 이동한다.
- 현재 노드에 "ab"를 표시한다.
"car"의 경우
- 현재 Head의 자식 노드에 "c"가 없으므로 Head의 자식 노드로 "c"를 추가해준다.
- "abc"를 추가해준 방법과 동일하게 진행한다.
- "r"노드에 "car"를 표시한다.
탐색
- "abc" 문자열 탐색
- Head의 자식에 a가 속해있으므로 a 노드로 이동.
- a의 자식에 b가 속해있으므로 b 노드로 이동.
- b의 자식에 c가 속해있으므로 c 노드로 이동.
- 문자열 탐색이 종료되었고, c 노드의 데이터에 abc가 존재하므로, "abc"라는 문자열이 존재한다.
- "ca" 문자열 탐색
- Head의 자식에 c가 속해있으므로 c 노드로 이동.
- c의 자식에 a가 속해있으므로 a 노드로 이동.
- 문자열 탐색이 종료되었지만, a 노드에는 데이터가 존재하지 않기에, "ca"라는 문자열은 존재하지 않는다.
트라이(Trie) 장단점
장점
1. 문자열을 빠르게 찾을 수 있다.
2. 문자열 추가와 탐색 모두 O(M)만에 가능하다.
단점
1. 메모리의 크기가 너무 크다.
2. 총 메모리는 O(포인터 크기 * 포인터 배열 개수 * 총 노드의 개수)가 필요하다.
이러한 단점을 해결하기 위해 보통 map 등을 이용하여 필요한 노드만 메모리를 할당하는 방식으로 사용하는데, 문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 까다롭다.
트라이(Trie) 시간 복잡도
제일 긴 문자열의 길이: M
총 문자열들의 수: N
- 생성 시 시간 복잡도: O(M*N)
- 삽입 시 시간 복잡도: O(M)
- 탐색 시 시간 복잡도: O(M)
- 탐색(map으로 만든 경우) 시 시간 복잡도: O(MlogN)
