트라이(Trie) 자료구조

트라이(Trie) 자료구조란?

트라이(Trie)는 문자열을 효율적으로 탐색하고 저장하기 위한 트리 형태의 자료구조입니다. 특히 문자열이 포함되어 있는지 빠르게 확인하거나, 자동 완성 및 검색 추천과 같은 기능을 구현할 때 유용하게 사용됩니다. 트라이는 문자열의 접두사(prefix)를 기반으로 데이터를 관리하여, 중복되는 접두사를 공유하여 메모리를 절약합니다.

트라이의 특징

• 트라이는 루트에서부터 문자열의 각 문자를 노드로 가지는 트리 형태입니다.
• 같은 접두사를 가진 문자열끼리는 공통의 경로를 공유합니다.
• 문자열의 길이가 길어져도 탐색 속도는 문자열의 길이에 비례하여 빠르게 유지됩니다.
• 검색, 자동 완성, 사전 검색 등에 효율적으로 사용됩니다.

트라이의 구조

• 각 노드는 문자와 자식 노드에 대한 참조를 가지고 있습니다.
• 마지막 문자 노드는 보통 "end of word" 표시를 통해 문자열의 끝임을 나타냅니다.

예시: ["car", "cat", "dog"] 저장 시

root
├── c
│   └── a
│       ├── r [끝]
│       └── t [끝]
└── d
    └── o
        └── g [끝]

트라이의 장단점

장점

• 문자열 탐색 속도가 빠릅니다.
• 접두사를 공유하여 메모리를 절약할 수 있습니다.
• 자동 완성과 같은 기능 구현에 적합합니다.

단점

• 각 노드가 여러 개의 자식 노드를 저장하는 구조로 인해 메모리 사용량이 많아질 수 있습니다.
• 구현이 다소 복잡합니다.

트라이의 활용 사례

• 검색 엔진의 자동 완성 및 추천 시스템
• 전화번호부와 같은 연락처 관리 시스템
• 사전 및 스펠 체크 프로그램
• IP 라우팅 테이블

간단한 구현 예시 (자바)

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean endOfWord;

    TrieNode() {
        endOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node = node.children.computeIfAbsent(ch, c -> new TrieNode());
        }
        node.endOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return false;
        }
        return node.endOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        String[] words = {"car", "cat", "dog"};
        for (String word : words) {
            trie.insert(word);
        }

        System.out.println(trie.search("car"));  // true
        System.out.println(trie.search("cap"));  // false
    }
}

트라이(Trie)는 문자열을 다룰 때 매우 유용하고 효율적인 자료구조입니다. 다양한 문자열 검색 및 추천 기능을 구현할 때 적극적으로 활용해 보시길 바랍니다.