🔤 Trie (트라이) 완벽 정리 - 문자열 탐색에 최적화된 자료구조

---

✅ Trie란?

Trie는 문자열 탐색에 최적화된 트리 기반 자료구조다.
접두사(prefix)를 기준으로 노드를 구성하며, 단어들의 공통된 접두사를 한 번만 저장하므로 메모리 효율이 뛰어나다.
자동완성, 사전 검색, 추천 시스템 등에 널리 사용된다.

---

✅ 특징

• 루트 노드는 비어 있으며, 각 간선은 하나의 문자에 해당한다.
• 문자열의 각 문자를 한 단계씩 내려가며 저장한다.
• 공통 접두사는 노드를 공유하여 저장 공간을 줄인다.
• 각 노드는 해당 지점에서 단어가 끝나는지를 나타내는 is_end 표시를 가질 수 있다.

---

✅ Trie 구조 예시

단어: ["cat", "car", "cart", "dog"] 를 삽입하면 다음과 같은 구조가 된다.

(root)
  ├── c
  │   └── a
  │       ├── t  (is_end=True)  ← "cat"
  │       └── r  (is_end=True)  ← "car"
  │           └── t  (is_end=True)  ← "cart"
  └── d
      └── o
          └── g  (is_end=True)  ← "dog"

---

✅ 주요 연산

🔹 삽입 (Insert)

• 문자열의 각 문자를 따라 노드를 타고 내려가며 없으면 새로 생성한다.
• 마지막 문자 노드에 is_end = True로 표시한다.

🔹 검색 (Search)

• 문자열의 각 문자를 따라 내려가며 노드를 찾는다.
• 마지막 문자 노드의 is_end가 True이면 문자열이 존재한다.

🔹 접두사 검사 (StartsWith)

• 주어진 prefix가 존재하는지 확인한다.
• is_end와는 관계없이 노드가 존재하면 된다.

---

✅ 파이썬 구현 예제

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    # 단어 삽입
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    # 단어 검색
    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_end

    # 접두사 검색
    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

    # 공통 로직 분리
    def _find_node(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")
trie.insert("dog")

print(trie.search("car"))       # True
print(trie.search("care"))      # False
print(trie.starts_with("ca"))   # True
print(trie.starts_with("do"))   # True
print(trie.starts_with("du"))   # False

---

🎯 마무리 요약

• Trie는 문자열 탐색, 특히 접두사 기반 탐색에서 뛰어난 성능을 가진다.
• 단어 삽입, 검색, 접두사 검사는 모두 O(문자열 길이) 만큼의 시간복잡도를 가진다.
• 문자열이 많은 상황에서도 공통 접두사를 공유하므로 메모리를 절약할 수 있다.
• 검색, 자동완성, 추천 시스템 등에서 매우 유용하게 쓰인다.