[자료구조] Trie (트라이) c++ 구현, 설명

Trie(트라이)

트라이라는 것은 문자열 집합을 관리하는 트리이다.

하나의 간선은 하나의 알파벳을 나타내고,

트리를 내려가면서 만나는 간선의 알파벳을 모두 이어주면 원래의 문자열을 얻을 수 있다.

트라이

*그림이 좀 잘못되었는데 문자열 집합 중 abd가 아니라 ad가 맞음.

여기서 T라는 것은 문자열의 끝을 표시하는 것으로 T까지 경로를 이어주면 원래 문자열이 나오게 되는것이다.

그래서 트라이에 들어있는 문자열은 abc, ad, e,eg, f 가 된다.

이러한 트라이는 문자열의 삽입/ 삭제/탐색의 시간복잡도는 O(문자열의 길이)로 해시와 같은 복잡도로 빠른 편에 속한다.

또한 트라이를 응용하여 해시로는 할 수 없는 것들을 할 수 있다.

에를 들면 접두사 찾기 등등. 또한 정렬의 효과를 낼 수도 있다.

 

구현한 코드는 알파벳이 소문자로 들어올 때 적용이 되는 코드이다.

 

응용문제

주어진 문자열에서 서로 다른 부분 문자열을 사전순으로 나열 했을 때 K번째 부분 문자열을 구하는 문제.

*최대 문자열의 길이는 400으로 가정함.

 

전체 코드는 github에 업로드 

-> https://github.com/goragoraki/Data-Structure