[자료구조] 트라이 (Trie)

트라이 : Trie

검색을 목적으로 하는 트리의 일종

동적인 set, 혹은 서로 관련이 있는 array를 저장하기 위해 주로 사용한다.

자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.

❓ 자동 완성에서 Trie를 사용하는 과정 참고

  https://biewoom.github.io/non%20linear%20ds/advanced%20ds/nodes%20ds/2020/04/14/Trie.html

 

 

 

Trie는 문자열들을 하나하나 쪼개어 tree 구조에 넣음으로써 검색을 더 빠르게 한다.

예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고,

다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다.

 

 같은 노드의 자식들은 같은 prefix를 갖게 된다.

 

 

https://mymusing.co/trie-data-structure/

 

 

 

트라이의 Big-O, 특징

Trie에 저장된 것 중 가장 긴 string의 길이를 m이라고 하면,

worst-case 탐색 시간이 O(m)이 걸린다.

 

M의 길이를 가지는 N개의 문자열에 대해서 부분문자열의 경우를 찾는 경우,

2중 for문을 통해 할 경우 O(M * N^2)의 시간복잡도를 가진다. 이렇게 되면 많은 문제에서 TLE(Time Limit Exceeded)를 만남

 

trie는 한개를 탐색할 때 O(M), 전체 O(MN)으로 풀 수가 있다.

물론 Trie를 생성할 때 O(MN)이 걸리지만 O(M * N^2) 보다 훨씬 짧다.
N의 개수가 늘어날 수록 훨씬 효과적일 것이다.

 

일반적인 트리와는 다르게, 가지가 요소 한개 혹은 여러개가 있는 레이블을 가질 수 있다. 이러한 특징 덕분에,

• 긴 String이고
• 작은 set이고
• 긴 prefix를 공유하는 string들

일 수록 유리하다고 한다.....

 

개선된 트라이

공간 사용을 최소한으로 하는 Trie

> 만약 각 노드가 유일한 자식이라면, 그 부모와 합쳐 버립니다.(루트노드를 제외)

원래는 각자 하나의 노드를 가졌어야할 외동 노드들이 모두 합쳐져 버렸으니까 

space-effient, space-optimized 되었다고 얘기한다고 함!

 

 

---

 

✔️ 참고

https://velog.io/@ansrjsdn/Trie-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JavaScript

https://juneyr.dev/2019-10-15/trie

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie