자료구조 Trie

trie란?

trie 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

trie의 예시

목적

정수형 자료에 대해 이진검색트리를 하면 O(log N)의 시간만에 원하는 데이터를 검색할 수 있다.

하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 L이라면 O(LlogN)의 시간 복잡도를 가지게 될 것이다.

하지만 트라이를 사용하면 O(L)의 시간만에 원하는 문자열을 검색할 수 있다.

시간복잡도

• 가장 긴 문자열의 길이를 L, 총 문자열의 수를 N이라고 할 때 시간 복잡도는 다음과 같다
• 생성시: O(N*L)
• 삽입, 탐색시: O(L)

직접 구현

백준 5052

https://twpower.github.io/187-trie-concept-and-basic-problem