Trie 자료구조

Trie(트라이)

Trie의 개요

Trie 는 트리 자료구조 중 하나이다. 특히 여러개의 문자열을 저장하는 자료구조인데 특정 문자열을 검색할 때 효율적이다.
가령 최대 길이가 m인 문자열 n개가 있는 집합에서 길이가 m인 임의의 문자열이 있는지 확인하려면 어떻게 해야할까?
단순히 직관적인 방법으로 하나씩 꺼내서 비교하면 된다. 하지만 최악의 경우 O(nm)의 시간복잡도가 소요된다.
그렇다면 Trie는 어떻게 문자열을 저장하길레 문자열을 검색할때 효율적일까?
바로 우리가 사전에서 단어를 찾듯이 문자열을 저장한다. 우리는 사전에서 "Apple"이란 단어를 찾을 때 다음과 같이 찾을것이다.

1. A가 있는 곳을 찾는다.   
2. 두번째 글자가 p인 곳을 찾고 세번째가 p인 곳을 찾는다. 
3. 마지막 글자까리 위와같은 방식으로 하여 "Apple"이란 글자를 찾는다.   

사전의 모든 단어를 비교하는 것이 아닌 A -> P -> P -> L -> E 순으로 단어를 찾아 나아갈 것이다.
Trie 자료구조는 사전과 같은 방식으로 문자열을 저장한 것이다.

Trie의 구조

트라이의 구조를 살펴보기 위해 Apple 사의 제품군을 예시로 보자!

IPHONE 이란 제품이 있는지 검색하기 위해 Trie를 사용하게 되면 IPHONE의 길이인 6번만 비교하며 탐색을 진행하면 된다.
Trie 구조로 진행하지 않게 된다면 모든 제품명과 비교해 가면서 찾아야 한다.
구조를 보면 알 수 있듯이 많은 공간을 사용하는 단점이 있다. 하지만 찾고자 하는 문자열의 길이의 속도만큼 빠른 탐색이 가능하다.

정리

정의

Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 자료구조  

시간복잡도

생성시 시간복잡도 : O(MN), M : 최대 문자열의 길이, N : 문자열의 개수
탐색시 시간복잡도 : O(M), M : 문자열의 길이 
삽입시 시간복잡도 : O(M), M : 문장열의 길이

장점

문자열을 빠르고 효율적으로 탐색 가능   
새로운 문자열을 삽입할 때에도 빠르게 가능  

단점

많은 공간(메모리)를 차지

---

정리하면서

문자열 탐색과 관련된 알고리즘을 풀다가 Trie라는 알고리즘을 알게되었다.
트리를 활용해서 이러한 작업도 가능하다는 것을 알게 되었고 문자열을 효율적으로 검색하는 방법을 알게되었다.
더욱더 열심히 공부하고 익혀나아가야겠다.

참고한 자료

https://namu.wiki/w/트라이
https://brunch.co.kr/@springboot/75
https://twpower.github.io/187-trie-concept-and-basic-problem