[Algorithm/알고리즘] Trie - 트라이 자료구조 이해하기

트라이(Trie) 자료구조

트라이(Trie) 자료구조는 문자열을 효율적으로 저장하고 검색하기 위해 고안된 트리 기반 자료구조입니다. 이 글에서는 트라이의 기본 개념부터 동작 원리, 장점, 활용 사례, 예제 코드, 그리고 기본 연산에 관한 예제까지 단계별로 설명하겠습니다.

1. 트라이의 기본 개념

트라이는 "프리픽스 트리(prefix tree)" 또는 "디지털 트리(digital tree)"라고도 불리며, 주로 문자열의 접두사를 공유하는 구조적 특징을 가지고 있습니다. 각 노드는 하나의 문자를 저장하고, 자식 노드 배열을 통해 다음 문자를 가리킵니다. 트리의 루트 노드는 비어 있으며, 각 노드는 26개의 자식 노드를 가질 수 있습니다(영어 알파벳 기준)​.

2. 트라이의 구조와 동작 원리

트라이는 트리 구조를 기반으로 하며, 각 노드는 문자를 저장하고 자식 노드로의 참조를 포함합니다. 트라이의 기본 구조는 다음과 같습니다:

트라이 기본 구조:

• 루트 노드(Root Node): 트라이의 시작점으로, 일반적으로 비어 있습니다.
• 자식 노드(Children Nodes): 각 노드는 26개의 자식 노드를 가질 수 있으며(영어 알파벳 기준), 각 자식 노드는 해당 문자를 저장합니다.
• 불리언 값(Boolean Flag): 각 노드는 isEndOfWord라는 불리언 값을 가지고 있으며, 이 값은 해당 노드가 단어의 끝을 나타내는지 여부를 나타냅니다.

예시:

apple"과 "app"을 트라이에 저장한 경우, "app"은 "apple"의 접두사를 공유하게 됩니다. 트라이의 구조는 다음과 같습니다.

         (root)
          /  
         a
        /
       p
      /
     p
    / \
   l   (isEndOfWord=True for "app")
  /
 e
(isEndOfWord=True for "apple")

삽입 과정:

1. 삽입할 문자열의 각 문자를 루트부터 차례로 처리합니다.
2. 현재 노드에서 해당 문자의 자식 노드가 없으면 새 노드를 생성합니다.
3. 문자열의 마지막 문자를 처리할 때 해당 노드를 isEndOfWord로 표시합니다.

검색 과정:

1. 검색할 문자열의 각 문자를 루트 노드부터 차례로 따라 내려갑니다.
2. 현재 문자의 자식 노드가 없으면 문자열이 존재하지 않음을 반환합니다.
3. 문자열의 마지막 문자까지 도달하면 isEndOfWord 값을 확인하여 문자열의 존재 여부를 반환합니다.

3. 트라이의 특징

1. 효율적인 검색: 트라이의 검색 시간 복잡도는 문자열의 길이에 비례하는 O(L)입니다. 이는 해시 테이블의 평균 검색 시간 복잡도인 O(1)보다 느릴 수 있지만, 해시 충돌이 발생하지 않으며 접두사 검색(prefix search)에 매우 유리합니다​.
2. 메모리 사용 최적: 트라이는 각 노드가 자식 노드에 대한 포인터 배열을 포함하므로, 많은 문자열을 저장할 때 메모리 사용이 증가할 수 있습니다. 하지만, 공통 접두사를 공유함으로써 메모리 사용을 최적화할 수 있습니다​.
3. 접두사 기반 검색: 트라이는 접두사 기반 검색에 매우 효율적입니다. 예를 들어, "app"으로 시작하는 모든 단어를 찾는 데 매우 적합합니다. 이는 자동 완성 기능, 사전 검색 등에 유용하게 사용됩니다​.
4. 정렬된 데이터 저장: 트라이는 본질적으로 정렬된 구조를 가지고 있어, 사전 순으로 데이터를 저장하고 검색할 수 있습니다. 이는 문자열 정렬, 사전 구현 등에 유용합니다.
5. 데이터 중복 방지: 동일한 접두사를 공유하는 문자열을 같은 경로로 저장함으로써 데이터 중복을 방지하고 저장 공간을 절약할 수 있습니다.
6. 해시 충돌 없음: 해시 테이블과 달리 해시 충돌 문제가 없으므로 안정적인 성능을 보장합니다.

4. 트라이의 단점

트라이 자료구조에는 몇 가지 단점이 존재합니다. 가장 큰 문제는 메모리 사용량입니다. 각 노드는 최대 26개의 포인터를 저장해야 하므로, 특히 입력되는 문자열들이 접두사를 전혀 공유하지 않는 경우 메모리 사용량이 매우 커질 수 있습니다. 이러한 경우 트라이에는 입력되는 문자열들의 전체 길이만큼의 노드가 필요하게 되어 메모리 효율이 떨어집니다.

5. 트라이의 예제 코드 (Python)

아래는 트라이 자료구조를 파이썬으로 구현한 예제 코드입니다. 이 코드에는 삽입, 검색, 삭제 연산이 포함되어 있습니다.

class TrieNode:
    def __init__(self):
        self.isEndOfWord = False  # 단어의 끝을 표시하는 불리언 값
        self.children = {}        # 자식 노드를 저장하는 딕셔너리

class Trie:
    def __init__(self):
        self.root = TrieNode()  # 트리의 루트 노드를 초기화

    def insert(self, word):
        node = self.root  # 루트 노드부터 시작
        for char in word:  # 문자열의 각 문자를 처리
            if char not in node.children:  # 자식 노드가 없으면
                node.children[char] = TrieNode()  # 새로운 자식 노드를 생성
            node = node.children[char]  # 다음 노드로 이동
        node.isEndOfWord = True  # 문자열의 마지막 노드를 단어의 끝으로 표시

    def search(self, word):
        node = self.root  # 루트 노드부터 시작
        for char in word:  # 문자열의 각 문자를 처리
            if char not in node.children:  # 자식 노드가 없으면
                return False  # 문자열이 존재하지 않음을 반환
            node = node.children[char]  # 다음 노드로 이동
        return node.isEndOfWord  # 문자열의 마지막 노드가 단어의 끝인지 반환

    def delete(self, word):
        self._delete(self.root, word, 0)  # 재귀적으로 삭제 함수 호출

    def _delete(self, node, word, depth):
        if node is None:
            return False  # 노드가 존재하지 않으면 False 반환

        if depth == len(word):
            if node.isEndOfWord:
                node.isEndOfWord = False  # 단어의 끝 표시를 해제
                return len(node.children) == 0  # 자식 노드가 없으면 True 반환
            return False  # 단어의 끝이 아니면 False 반환

        char = word[depth]  # 현재 깊이의 문자
        if char in node.children:
            shouldDeleteCurrentNode = self._delete(node.children[char], word, depth + 1)
            if shouldDeleteCurrentNode:  # 자식 노드를 삭제해야 하면
                del node.children[char]  # 자식 노드를 삭제
                return len(node.children) == 0  # 현재 노드가 자식이 없으면 True 반환
        return False  # 자식 노드가 있으면 False 반환

# 트라이 사용 예시
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # True
print(trie.search("app"))    # False
trie.delete("apple")
print(trie.search("apple"))  # False

코드 설명

• TrieNode 클래스:
  • __init__ 메서드:
    • isEndOfWord를 False로 초기화하고, 자식 노드를 저장할 딕셔너리를 생성합니다.
• Trie 클래스:
  • __init__ 메서드:
    • 루트 노드를 초기화합니다.
  • insert 메서드:
    • 문자열의 각 문자를 처리하면서 현재 노드의 자식 노드가 없으면 새로운 노드를 생성합니다.
    • 문자열의 마지막 문자를 처리할 때 해당 노드를 단어의 끝으로 표시합니다.
  • search 메서드:
    • 문자열의 각 문자를 처리하면서 현재 노드의 자식 노드가 없으면 문자열이 존재하지 않음을 반환합니다.
    • 문자열의 마지막 문자까지 도달하면 해당 노드가 단어의 끝인지 여부를 반환합니다.
  • delete 메서드:
    • 재귀적으로 문자열을 탐색하여 노드를 삭제합니다.
    • 문자열의 끝에 도달하면 isEndOfWord를 False로 설정하고, 자식 노드가 없으면 현재 노드를 삭제합니다.

6. 트라이의 실제 활용 사례

1. 검색 엔진의 자동 완성 기능: 사용자가 입력하는 문자열의 접두사에 해당하는 단어를 실시간으로 추천하는 기능에 트라이를 사용합니다. 예를 들어, Google 검색창에 단어를 입력할 때 자동으로 제안되는 단어들이 트라이를 통해 효율적으로 구현됩니다​.
2. 사전 구현: 트라이는 단어의 저장과 검색이 효율적이므로, 디지털 사전에서 단어를 저장하고 찾는 데 유용합니다​.
3. 문자열 매칭 알고리즘: 다양한 문자열 매칭 문제를 해결하는 데 사용됩니다. 예를 들어, 긴 텍스트에서 특정 패턴을 찾는 문제에서 트라이는 효율적으로 패턴을 검색할 수 있습니다.

트라이 사용 팁

알고리즘 문제를 풀 때 트라이를 사용하는 것이 적합한지 판단하는 몇 가지 팁이 있습니다:

• 문제에서 입력되는 문자열들의 전체 길이를 명시하는 경우, 트라이를 사용하여 해결할 가능성을 고려해보세요. 특히 문자열을 탐색하는 문제에서 이러한 힌트가 제공된다면 트라이를 사용해야 할 확률이 높습니다.

결론

트라이 자료구조는 문자열을 효율적으로 저장하고 검색하는 데 매우 유용한 데이터 구조입니다. 특히, 접두사를 공유하는 특성을 통해 메모리 사용을 최적화하고, 일정한 시간 복잡도로 빠른 검색을 제공합니다. 다양한 문자열 처리 문제를 해결하는 데 트라이를 활용할 수 있으며, 이를 통해 성능을 크게 향상시킬 수 있습니다.