[DS] Trie(트라이)

❗Trie란?

Trie(트라이)는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반 자료구조이다. 특히 문자열의 접두사(prefix) 검색에 강점이 있고 자동 완성, 사전 검색, 문자열 집합에서의 중복 확인 등에 유용히다
각 노드는 하나의 문자를 저장하고 자식 노드로 이어지는 링크들을 가지며 루트에서 시작해 각 문자를 따라가면 하나의 문자열이 완성된다.
 

• 루트 노드는 아무 문자도 저장하지 않고 자식 노드들로 각 문자가 연결
• 각 노드는 문자와 자식 노드들을 가짐
• 단어의 끝을 표시하는 종료 노드가 필요하며 보통 플래그로 설정

 

 ❗Trie의 복잡도

삽입/탐색 시간복잡도	O(L) (L은 문자열의 길이)  문자열의 길이에 비례하기 때문에 길이가 짧을수록 빠른 퍼포먼스를 낼 수 있다.
공간복잡도	O(∑L) (저장된 모든 문자열의 길이 합) 문자열의 접두사를 공유해서 중복되는 문자들이 저장되는 공간은 줄어든다. 하지만 각 문자에 대한 노드를 따로 저장하기 때문에 다소 많은 공간을 차지할 수 있다.

 

  ❗Trie의 장점과 단점

장점	빠른 검색: 문자열의 길이에 비례하여 매우 빠른 검색이 가능 접두사 검색에 강점: 접두사를 기준으로 한 검색 및 자동 완성 기능을 쉽게 구현할 수 있음 공통 접두사 활용: 동일한 접두사를 가지는 문자열들이 공간을 공유하여 효율적으로 관리됨
단점	공간 낭비: 모든 문자에 대해 노드를 생성해야 해서 저장하는 데이터의 양이 많을 경우 메모리 사용량이 증가할 수 있음 저장 공간 최적화 어려움: 대규모 문자열 데이터에서 Trie는 저장 공간을 최적화하기 어려움