Trie 자료구조

Trie 자료구조에 대한 정리

오늘은 Trie(트라이) 자료구조에 대해 공부한 내용을 정리해보겠습니다.

---

Trie 자료구조란?

Trie는 문자열을 효율적으로 저장하고 검색하기 위해 사용되는 자료구조입니다. 이 자료구조는 문자열들의 공통 접두사(prefix)를 활용하여 저장 공간을 절약하고, 빠른 탐색이 가능하도록 설계되었습니다.

---

Trie의 구조와 특징

Trie 자료구조는 트리 형태로 구현되며, 각 노드는 하나의 문자를 저장합니다. 문자열의 공통 접두사를 하나의 경로로 묶고, 나머지 다른 부분을 하위 노드로 분리합니다.

구조

• Root Node: 모든 Trie는 항상 루트 노드에서 시작합니다.
• 노드: 각 노드는 하나의 문자를 저장합니다.
• 하위 노드: 자식 노드를 통해 다음 문자와 연결됩니다.
• isLast 플래그: 특정 노드가 문자열의 끝임을 표시하는 변수.

효율성

• 저장 공간 절약: 공통 접두사를 하나의 경로로 묶어 중복 데이터를 줄입니다.
• 탐색 시간 단축: 문자열의 길이에 비례하는 시간 복잡도(O(L))로 탐색 가능.

---

Trie의 동작 원리

1. 삽입 과정

• 문자열을 Trie에 삽입할 때, 루트 노드에서 시작하여 각 문자를 차례대로 트리에 추가합니다.
• 공통 접두사가 존재하면 해당 경로를 따라가고, 그렇지 않으면 새로운 노드를 생성합니다.
• 마지막 문자를 삽입한 노드에 isLast 플래그를 설정하여 문자열의 끝임을 표시합니다.

2. 탐색 과정

• 루트 노드에서 시작하여 문자열의 각 문자를 따라가며 노드가 존재하는지 확인합니다.
• 문자열의 마지막 문자까지 확인한 뒤, 해당 노드의 isLast 플래그를 통해 문자열이 Trie에 존재하는지 판단합니다.

---

삽입 알고리즘

1. 루트 노드에서 시작.
2. 문자열의 각 문자를 확인.
   • 현재 노드의 자식 노드에 해당 문자가 있는지 확인.
     • 있다면, 해당 노드로 이동.
     • 없다면, 새로운 노드를 생성하고 현재 노드의 자식 노드에 추가.
3. 문자열의 마지막 문자에 도달하면 isLast를 true로 설정.

삽입 코드 (Java)

public void insert(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        if (!current.getChildNodes().containsKey(ch)) {
            TrieNode newNode = new TrieNode(ch, false);
            current.getChildNodes().put(ch, newNode);
        }
        current = current.getChildNodes().get(ch);
    }
    current.setLast(true);
}

---

탐색 알고리즘

1. 루트 노드에서 시작.
2. 문자열의 각 문자를 확인하며 해당 문자를 가진 자식 노드가 있는지 탐색.
3. 문자열의 마지막 문자까지 탐색한 후, 현재 노드의 isLast 값을 확인.

탐색 코드 (Java)

public boolean search(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        if (!current.getChildNodes().containsKey(ch)) {
            return false; // 문자열이 존재하지 않음
        }
        current = current.getChildNodes().get(ch);
    }
    return current.isLast();
}

---

예제 동작

삽입 예제

1. CAT 삽입:
   • 루트 노드에서 C -> A -> T 순서대로 노드를 생성.
2. CAR 삽입:
   • 루트 노드에서 C -> A를 따라간 뒤, R 노드를 추가.

Trie 구조:

  (root)
    |
    C
    |
    A
   / \
  T   R

탐색 예제

1. CAT 탐색:
   • 루트 노드에서 C -> A -> T를 따라가며 존재 여부 확인.
   • T 노드의 isLast가 true이므로 존재.
2. CAR 탐색:
   • 루트 노드에서 C -> A -> R을 따라가며 확인.
   • R 노드의 isLast가 true이므로 존재.
3. CAN 탐색:
   • 루트 노드에서 C -> A까지 탐색한 뒤, N 노드가 없으므로 존재하지 않음.

---

Trie의 장점

1. 빠른 검색:
   • 문자열의 길이에 비례하는 시간 복잡도(O(L))로 탐색 가능.
2. 접두사 기반 검색:
   • 특정 문자열로 시작하는 모든 단어를 효율적으로 검색 가능.
3. 자동완성:
   • 접두사를 따라가며 자동완성 기능 구현 가능.

Trie의 단점

1. 공간 사용량:
   • 문자열의 개수가 많고 접두사가 적으면 많은 메모리를 사용.
2. 구현 복잡성:
   • 단순한 문자열 검색 문제에서는 배열이나 해시맵보다 구현이 복잡할 수 있음.

---

결론

Trie 자료구조는 문자열을 효율적으로 저장하고 검색하기 위한 강력한 도구입니다. 특히 접두사 검색, 자동완성, 사전 구현 등에서 매우 유용하며, 문자열 데이터와 관련된 다양한 문제를 해결할 수 있습니다. 다만, 공간 복잡도를 고려해 사용 여부를 판단해야 합니다.