트라이(Trie)란?
- 트라이 알고리즘은 문자열을 트리 구조로 저장해 빠르게 찾는 알고리즘 기법 중의 하나입니다.
- 보통 트리의 구조에는 단일 int형 변수를 저장하는 경우가 많은데, 이를 문자열 형태로 저장한다고 생각하면 됩니다.
- 검색어 자동완성, 사전 검색, 문자열 검사 등에 사용됩니다.
- 하나의 노드는 알파벳일 경우 26개의 자식노드, 숫자일 경우 10개의 자식 노드가 생길 수 있습니다. 또한, 한 노드당 그 만큼의 포인터 배열을 설정해주어야 하기 때문에 공간복잡도를 많이 소모합니다.
시간 복잡도
제일 긴 문자열의 길이를
L총 문자열들의 수를M이라 할 때 시간복잡도는 아래와 같습니다.
- 생성시 시간복잡도:
O(M x L), 모든 문자열들을 넣어야하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서O(M x L)만큼 걸립니다. 물론 삽입 자체만은 O(L)만큼 걸립니다.- 탐색시 시간복잡도: O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸립니다.
- 또, 한 문자열을 저장하게 되면 트리의 구조를 띄기 때문에 그 문자열의 접두사를 자동으로 모두 구할 수 있습니다.
