Trie란?
트라이(Trie)는 특별히 문자열에서 검색을 빠르게 해주는 tree 구조의 자료형이다. 일반적으로 Tree 자료구조와 같은 모양이지만 정수형을 저장하는 Tree와 다르게 문자(열)를 저장한다.
우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료구조이다.
Trie 등장 배경
위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 된다.
그러나 같은 이진트리 형태에 문자열을 저장한다면, 문자열의 최대길이가 M일 때 O(M*logN)의 시간 복잡도를 가지게 된다. 모든 노드를 방문할 때마다 문자열의 각 char를 또 방문하기 때문이다. 이러한 문제를 해결하기 위해 Trie를 사용하게 된다.
Trie 특징
문자열 전체를 하나의 노드에 저장하는게 아니라 한 레벨에 하나의 글자만을 저장하여, 문자열을 세로로 저장한다. 이때 문자열이 모두 똑같은 문자로 시작하는 것이 아니므로 루트노드는 비워준다. 따라서 문자열의 최대 길이가 M이라고 할 때 O(M)의 시간복잡도를 가지게 된다.
위 그림의 Trie에 저장된 문자는 cap, code, bus, box이다. 단어를 검색한다면 문자열의 한 단어씩 자식 노드와 비교해가면서 검색을 진행할 수 있다. cap을 검색한다면 c 자식 노드 > a 자식 노드 > p 자식 노드 순으로 진행된다. 따라서 이런 식으로 찾고자 하는 문자를 탐색하므로 문자열의 길이가 M 일 때, 탐색 시간 복잡도는 O(M)을 가지게 되므로 문자열 자료에 매우 효율적이다.
