Trie (트라이)

정의

• Trie (트라이)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 입니다.

시간 복잡도

• 제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때 시간복잡도는 아래와 같습니다.

• 생성시 시간 복잡도 : O(M*L),
  모든 문자열들을 넣어야 하니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 총, O(M*L)만큼 걸립니다.

• 탐색 시 시간 복잡도 : O(L)

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