[자료구조] Trie

🎯 Trie

---

트라이(Trie)는 검색 트리의 일종으로, 문자열 탐색에 사용되는 자료 구조입니다. 트라이는 문자열을 이진 검색 트리(Binary Search Tree)처럼 저장하지 않고, 각 노드의 문자열을 표현합니다. 이러한 방식으로 트라이는 문자열 검색 및 삽입에서 높은 성능을 보이며, 특히 문자열 검색에 대해 O(m)의 시간 복잡도를 가집니다. (m은 검색하는 문자열의 길이입니다.)

Trie의 구조

---

⭐️ {"A", "to", "tea", "ted", "ten", "i", "in", "inn"} 을 트라이로 구현

트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다.

또 트라이의 중요한 속성 중 하나는 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면, 찾고자 하는 문자열의 접두사를 얻을 수 있다.

예를 들어서 "tea"를 찾는다고 해보자.
t -> te -> tea의 순서로 탐색되므로 "tea"의 모든 접두사들이 다 구해지게 된다.

Trie 장단점

---

⭐️ Trie 장점

1. 검색에 높은 성능을 보입니다. 문자열의 길이와 상관없이 일정한 검색 시간을 보장합니다.
2. 검색어 자동완성, 철자 교정, 텍스트 압축 등에서 활용할 수 있습니다.
3. 문자열을 검색하는데 있어서 정확한 검색 결과를 보장합니다. 다른 자료구조와 달리 전체 문자열을 저장하기 때문입니다.

💀️ Trie 단점

1. 저장공간이 큽니다. 트라이는 모든 문자열을 저장하기 때문에, 저장공간이 불필요하게 낭비될 수 있습니다.
2. 트라이를 구현하기 위한 코드가 다소 복잡합니다. 따라서 개발 시간이 늘어날 수 있습니다.
3. 문자 집합이 크거나 문자열 길이가 길 경우, 트라이의 깊이가 너무 깊어져 검색 시간이 길어질 수 있습니다.

트라이는 검색 시간을 줄이는데 있어서 매우 효율적인 자료구조입니다. 그러나 저장공간의 비효율성과 구현의 복잡성 때문에, 상황에 따라서 적절한 자료구조를 선택하는 것이 중요합니다.