Jerry's Log

Trie

Posted: 2025-12-30 Tags: cs datastructure

contents

트라이(Trie)(발음: "트라이" 또는 "트리")는 문자열을 키로 사용하는 동적 데이터 세트를 저장하는 데 사용되는 특수한 트리 기반 자료구조입니다. 문자열을 접두사(Prefix) 단위로 쪼개어 저장하기 때문에 접두사 트리(Prefix Tree) 라고도 불립니다.

해시 맵(Hash Map)은 검색에 $O(1)$이 걸리지만, 트라이는 자동 완성 시스템이나 맞춤법 검사기와 같이 접두사 와 관련된 문제에서 독보적인 장점을 가집니다.

1. 구조 (The Structure) 🌳

왼쪽과 오른쪽 자식만 가지는 이진 트리와 달리, 트라이의 노드는 여러 개의 자식을 가질 수 있습니다 (영어 알파벳의 경우 보통 26개).

노드 구성 요소

트라이의 각 노드는 일반적으로 다음을 포함합니다.

  1. 자식 (Children): 자식 노드들을 가리키는 포인터 배열(또는 해시 맵). 소문자 영어의 경우 보통 크기 26의 배열(children[26])을 사용합니다.
  2. 단어 끝 표시 (IsEndOfWord - Boolean): 이 노드가 유효한 단어의 끝임을 알리는 플래그입니다.

시각화

"CAT", "CAR", "DOG" 라는 단어를 저장한다고 상상해 봅시다.

"CAT"과 "CAR"가 C $\rightarrow$ A 경로를 공유한다는 점에 주목하세요. 이 경로 공유 덕분에 트라이는 공통 접두사가 많은 데이터셋에서 메모리를 효율적으로 사용합니다.

2. 핵심 연산 (Core Operations) ⚙️

처리하려는 단어의 길이를 $L$이라고 합시다.

A. 삽입 (Insertion): $O(L)$

"APPLE"이라는 단어를 삽입하려면:

  1. 루트에서 시작합니다.
  2. 'A'에 대한 자식 링크가 있는지 확인합니다. 없으면 새 노드를 만듭니다. 그 노드로 이동합니다.
  3. 'P'에 대해 확인합니다. 없으면 만듭니다. 이동합니다.
  4. 'P', 'L', 'E'에 대해 반복합니다.
  5. 마지막 'E' 노드에서 isEndOfWord = true로 표시합니다.

B. 검색 (Search): $O(L)$

"APP"을 검색하려면:

  1. 루트에서 시작합니다.
  2. 'A' $\rightarrow$ 'P' $\rightarrow$ 'P' 링크를 따라갑니다.
  3. 만약 중간에 막히면(링크가 null이면), 단어는 존재하지 않는 것입니다.
  4. 마지막 노드에 도달하면 isEndOfWord를 확인합니다. true면 단어가 존재하는 것이고, false면 "APP"은 다른 단어(예: APPLE)의 접두사일 뿐 저장된 단어 자체는 아닙니다.

C. 접두사 검색 (StartsWith): $O(L)$

트라이가 가장 빛을 발하는 부분입니다. "AP"로 시작하는 단어가 있는지 확인하려면:

  1. 'A' $\rightarrow$ 'P' 링크를 따라갑니다.
  2. 끊기지 않고 전체 접두사를 순회하는 데 성공하면 true를 반환합니다. isEndOfWord 플래그를 확인할 필요가 없습니다.

3. 해시 맵과의 비교 ⚖️

HashMap<String, Boolean>이 있는데 굳이 트라이를 사용하는 이유는 무엇일까요?

특징 해시 맵 (Hash Map) 트라이 (Trie)
조회 시간 평균 $O(1)$. 하지만 문자열을 해싱하려면 전체를 읽어야 하므로 실질적으로는 $O(L)$. 엄격하게 $O(L)$.
접두사 검색 느림. 모든 키를 스캔해야 함 ($O(N \times L)$). 빠름. $O(L)$.
공간 오버헤드가 큼. 중복된 접두사가 개별적으로 저장됨 (예: "chair", "chat"은 "cha"를 두 번 저장). 최적화됨. 공유된 접두사("cha")는 한 번만 저장됨.
순서 정렬되지 않음. 구조의 특성상 알파벳 순으로 정렬됨.

4. 실제 사용 사례 🛠️

  1. 자동 완성 (Autocomplete / Typeahead): 검색창에 "goog"를 입력하면, 트라이는 g-o-o-g를 순회한 뒤 유효한 모든 자손(google, goggles 등)을 반환합니다.
  2. 맞춤법 검사기 (Spell Checkers): 입력과 1글자 차이 나는 단어들을 쉽게 찾을 수 있습니다.
  3. IP 라우팅: 라우터에서 최장 접두사 일치(Longest Prefix Match)를 찾기 위해 IP 주소를(이진 문자열로) 저장합니다.
  4. 단어 게임: 보글(Boggle)이나 스크래블 같은 게임의 해답을 효율적으로 찾습니다.

5. 구현 예제 (Java)

다음은 소문자 알파벳을 처리하는 깔끔한 구현입니다.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 트라이에 단어 삽입
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // 'a'는 0, 'b'는 1로 매핑...
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isEndOfWord = true;
    }

    // 단어가 트라이에 존재하는지 확인 (정확히 일치)
    public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEndOfWord;
    }

    // 해당 접두사로 시작하는 단어가 트라이에 있는지 확인
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    // 순회를 돕는 헬퍼 함수
    private TrieNode getNode(String str) {
        TrieNode curr = root;
        for (char c : str.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                return null;
            }
            curr = curr.children[index];
        }
        return curr;
    }
}

요약

트라이는 구조적으로 약간의 복잡성을 감수하는 대신 접두사 관련 연산에서 엄청난 효율성을 제공합니다. 검색 바, 사전, 또는 IP 라우터를 구축한다면 트라이가 바로 표준 자료구조입니다.

references

Related Posts