트라이(Trie)

트라이(Trie)란?

• 문자열을 저장하는 자료구조에서 가장 효율적인 문자열 검색 알고리즘이다.
• 원하는 원소를 찾는 작업을 O(n)에 해결할 수 있는 자료구조
• 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다.
• 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.

예시

• 문자열 4개 {"bee", "can", "cat", "cd"}를 가지고 있다고 생각해본다. 트라이는 위와 같이 형성된다.
• 루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않는다.
• 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

예를 더 들어보자

• can은 c -> ca -> can이 되고, can의 접두사에는 c, ca 가 존재한다.
• 이때 ca는 문자열에서 나타난 종류 중 하나이다. 즉, can이 ca를 포함하는 것도 트라이에서 알 수 있게된다.
• 이러한 내용들 때문에 트라이는 접두사 트리(Prefix Tree)라고도 불린다.
• 이러한 과정이 이루어지는 동안의 시간 복잡도는 문자열 길이 만큼 시간이 든 것이다.
• 이러한 트라이를 생성해두면, 결국 원하는 단어(원소)를 찾을때 O(문자열길이)의 시간만에 찾아낼 수 있다.

---

트라이의 단점

트라이의 치명적인 단점은 공간 복잡도에서 나타난다.

트라에서 O(문자열길이)인 시간이 나오기 위해서는 다음 문자를 가리키는 노드가 필요하다.

예를 들어 알파벳에 대해 트라이를 형성해야 한다고 한다면 a~z인 총 26개의 포인터 배열을 가지고 있어야한다.

즉 최종 메모리는 (포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수)가 된다

 

 

 

 

 

 

출처

https://www.crocus.co.kr/1053

위키백과

brunch.co.kr/@springboot/75

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