[CS] 자료 구조 (3) : 트라이 (Trie)

트라이(Trie)

문자열에서 검색을 빠르게 도와주는 자료구조이다.

시간 복잡도 : 정수형에서 이진탐색트리를 이용하면 O(logN), 문자열에서 적용했을 때는 문자열 최대 길이가 M이면 O(M*logN)이 되지만 트라이를 활용하면 O(M)으로 문자열 검색이 가능하다.

 

예시 그림에서 주어지는 배열의 총 문자열 개수는 8개인데, 트라이를 활용한 트리에서도 마지막 끝나는 노드마다 '네모' 모양으로 구성된 것을 확인하면 총 8개다.