트라이(Trie) 란?

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다.

원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 **O(logN)**의 시간이 걸리게 된다.

하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에

원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다.

따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다.

이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다.

쉽게 말해, "문자열을 빠르게 탐색할 수 있는 자료구조"이다.

 

트라이(Trie) 자료구조의 장/단점

트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다.

더불어, 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에

문자열의 추가와 탐색 모두 O(M)만에 가능하다.

반면에 트라이의 단점은 필요한 메모리의 크기가 너무 크다는 점이다.

문자열이 모두 영소문자로 이루어져 있다고 해도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다.

최악의 경우에는 집합에 포함되는 문자열들의 길이의 총합만큼 노드가 필요하므로, 총메모리는

**O(포인터 크기 * 포인터 배열 개수 * 총노드의 개수)**가 된다.

만약, 1000자리의 문자열이 1000개만 들어온다고 하더라도 100만 개의 노드가 필요하고, 포인터의 크기가 8byte라고 하면 약 200MB의 메모리가 필요하게 된다.

따라서, 이 단점을 해결하기 위해서 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 꽤나 까다롭다.

또한, 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다.