Trees: Trie (트라이)

 

Trie (접두사 트리) - 동기

 

우리가 왜 trie가 필요한지에 대한 동기를 살펴봅시다.

 

예를 들어, 오이(cucumbers), 콜리플라워(cauliflower), 토마토(tomatoes) 같은 여러 채소가 들어 있는 큰 상자가 있다고 해 봅시다.

만약 이 채소들을 이름 기준으로 정리하고 싶다면, 우리는 먼저 더 작은 상자들을 준비해서 알파벳 각 글자를 이름표로 붙일 수 있을 거예요.

예를 들어, "A"로 시작하는 채소들은 "A" 상자에 넣는 식으로요.

 

접두사(prefix)가 같은 단어들을 처리하는 방식

Trie에서는 중복되는 접두사를 공유된 경로로 나타내어 공간을 절약하고 효율적으로 구조화할 수 있음

 

Trie의 계층 구조: 

상자 안에 또 상자를 넣는 방식으로, 단어의 각 글자마다 하나씩 노드를 추가해 나가는 방식

결국, Trie는 트리 구조를 가지며, 루트에서부터 각 글자를 따라 내려가는 방식

 

이제 "c" 상자 안에 각 채소 이름의 두 번째 글자를 이름표로 단 작은 상자들을 넣게 되면, "cauliflower"와 "cabbage"를 같은 상자 구조 안에 넣을 수 있게 됩니다.

이런 식으로 알파벳의 모든 글자에 대해 계속해서 작은 상자들을 더 큰 상자 안에 넣는 식으로 구조를 만들 수 있습니다.

 

Trie는 종종 Prefix Tree(접두사 트리) 라고도 불리는데, 그 목적을 더 잘 설명해주기 때문입니다.

Trie는 주어진 접두사를 기반으로 단어를 찾을 수 있는 트리 기반의 자료구조입니다.

이 작업은 **O(w)**의 시간복잡도로 수행되며, 여기서 w는 단어의 길이를 의미합니다.

이는 우리가 단어의 각 글자마다 트리를 따라 내려가기만 하면 되기 때문입니다.

 

모두 단어의 길이에 비례하는 시간으로, 매우 빠르고 일관된 성능을 보장

---

 

삽입 및 검색 시간이 : Constant time O(1)

 

# TrieNode 클래스는 Trie(접두사 트리)의 각 노드를 정의합니다.
class TrieNode:
    def __init__(self):
        # children은 자식 노드들을 담는 딕셔너리입니다.
        # 키는 문자(char), 값은 해당 문자를 따라간 다음 TrieNode입니다.
        self.children = {}
        # word는 이 노드가 하나의 단어의 끝을 나타내는지를 표시하는 플래그입니다.
        self.word = False

# Trie 클래스는 전체 Trie 구조를 정의하고, 삽입(insert), 검색(search), 접두사 검색(startsWith) 기능을 제공합니다.
class Trie:
    def __init__(self):
        # Trie의 루트 노드를 생성합니다. 루트는 비어 있는 TrieNode입니다.
        self.root = TrieNode()
    
    # 단어를 Trie에 삽입하는 함수입니다.
    def insert(self, word):
        # 루트부터 시작하여 글자를 하나씩 따라가며 노드를 구성합니다.
        curr = self.root
        for c in word:
            # 현재 글자가 자식 노드에 없으면 새로운 TrieNode를 생성해서 추가합니다.
            if c not in curr.children:
                curr.children[c] = TrieNode()
            # 현재 노드를 자식 노드로 이동시킵니다.
            curr = curr.children[c]
        # 단어의 마지막 글자에 해당하는 노드에 word 플래그를 True로 설정하여 단어의 끝임을 표시합니다.
        curr.word = True

    # 완전한 단어가 Trie에 존재하는지 검색하는 함수입니다.
    def search(self, word):
        # 루트부터 시작하여 글자를 하나씩 따라갑니다.
        curr = self.root
        for c in word:
            # 만약 글자가 존재하지 않는다면 해당 단어는 Trie에 없습니다.
            if c not in curr.children:
                return False
            # 자식 노드로 이동합니다.
            curr = curr.children[c]
        # 마지막 노드의 word 플래그가 True일 경우, 완전한 단어로 인정합니다.
        return curr.word

    # 주어진 접두사(prefix)로 시작하는 단어가 Trie에 존재하는지를 확인하는 함수입니다.
    def startsWith(self, prefix):
        # 루트부터 시작하여 접두사를 구성하는 글자를 하나씩 따라갑니다.
        curr = self.root
        for c in prefix:
            # 접두사에 포함된 글자가 없는 경우 False 반환
            if c not in curr.children:
                return False
            # 자식 노드로 이동
            curr = curr.children[c]
        # 모든 접두사 글자를 성공적으로 따라갔다면 True 반환
        return True