Trie — 문자열 검색을 O(L)에 끝내는 자료구조

검색창에 "app"을 치면 "apple", "application", "appetizer"가 즉시 제안됩니다. 수백만 개의 단어 중에서 어떻게 이렇게 빠를까요?

Trie란

Trie(트라이) 는 문자열의 각 문자를 트리의 간선으로 표현하는 자료구조입니다. "retrieval"에서 이름이 유래했고, 접두사 트리(prefix tree)라고도 부릅니다.

PLAINTEXT

          (root)
         /   |   \
        a    b    c
       /     |
      p      a
     / \     |
    p   e    t
    |
    l
    |
    e

위 Trie에는 "apple", "ape", "bat"이 저장되어 있습니다. "app"까지 내려가면 그 아래 모든 단어를 효율적으로 찾을 수 있습니다.

왜 필요한가

해시맵으로도 문자열을 O(1)에 찾을 수 있지만, Trie만의 장점이 있습니다.

**접두사 검색 **: "app"으로 시작하는 모든 단어 찾기 → 해시맵은 불가능, Trie는 가능
** 자동 완성 **: 타이핑할 때마다 후보를 즉시 제안
** 사전순 정렬 **: Trie를 순회하면 자동으로 사전순
** 공통 접두사 공유 **: "apple"과 "application"이 "appl"을 공유하여 메모리 절약

동작 원리

Trie 노드 구조

JAVA

public class Trie {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26]; // 소문자 알파벳
        boolean isEnd = false; // 이 노드에서 끝나는 단어가 있는지
        int count = 0;         // 이 접두사를 가진 단어 수 (선택)
    }

    private TrieNode root = new TrieNode();
}

삽입

문자열의 각 문자를 따라 트리를 내려가며, 없는 노드는 새로 만듭니다.

JAVA

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) {
            node.children[idx] = new TrieNode();
        }
        node = node.children[idx];
        node.count++; // 접두사 카운트 증가
    }
    node.isEnd = true;
}

검색

문자열의 각 문자를 따라 내려가다가, 중간에 null을 만나면 없는 것이고, 끝까지 도달하면 isEnd를 확인합니다.

JAVA

public boolean search(String word) {
    TrieNode node = findNode(word);
    return node != null && node.isEnd;
}

public boolean startsWith(String prefix) {
    return findNode(prefix) != null;
}

private TrieNode findNode(String s) {
    TrieNode node = root;
    for (char c : s.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) return null;
        node = node.children[idx];
    }
    return node;
}

삭제

삭제는 약간 복잡합니다. 단어를 삭제하되, 다른 단어의 접두사 경로는 유지해야 합니다.

JAVA

public boolean delete(String word) {
    return delete(root, word, 0);
}

private boolean delete(TrieNode node, String word, int depth) {
    if (node == null) return false;

    if (depth == word.length()) {
        if (!node.isEnd) return false; // 단어가 없음
        node.isEnd = false;
        return isEmpty(node); // 자식이 없으면 노드 삭제 가능
    }

    int idx = word.charAt(depth) - 'a';
    if (delete(node.children[idx], word, depth + 1)) {
        node.children[idx] = null;
        node.count--;
        return !node.isEnd && isEmpty(node);
    }
    node.count--;
    return false;
}

private boolean isEmpty(TrieNode node) {
    for (TrieNode child : node.children) {
        if (child != null) return false;
    }
    return true;
}

자동 완성 구현

접두사 노드까지 이동한 후, 서브트리를 DFS로 탐색하면 됩니다.

JAVA

public List<String> autocomplete(String prefix, int limit) {
    List<String> result = new ArrayList<>();
    TrieNode node = findNode(prefix);
    if (node == null) return result;

    dfsCollect(node, new StringBuilder(prefix), result, limit);
    return result;
}

private void dfsCollect(TrieNode node, StringBuilder sb, List<String> result, int limit) {
    if (result.size() >= limit) return;

    if (node.isEnd) {
        result.add(sb.toString());
    }

    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            sb.append((char) ('a' + i));
            dfsCollect(node.children[i], sb, result, limit);
            sb.deleteCharAt(sb.length() - 1); // 백트래킹
        }
    }
}

메모리 최적화 — HashMap 기반 Trie

알파벳이 26개가 아닌 경우(유니코드 등), 배열 대신 HashMap을 사용합니다.

JAVA

private static class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

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

시간/공간 복잡도

연산	시간 복잡도	비고
삽입	O(L)	L = 문자열 길이
검색	O(L)
접두사 검색	O(L + K)	K = 결과 문자열들의 총 길이
삭제	O(L)

공간은 최악의 경우 O(N × L × A)입니다 (N: 문자열 수, L: 평균 길이, A: 알파벳 크기). 하지만 접두사를 공유하므로 실제로는 더 적습니다.

백엔드/실무 연결

Spring PathPatternParser

Spring MVC의 URL 패턴 매칭은 Trie와 유사한 구조를 사용합니다. URL 경로를 / 기준으로 세그먼트를 나누고, 트리 형태로 관리합니다.

JAVA

// Spring의 URL 패턴이 내부적으로 트리 구조
// /api/users/{id}  → [api] → [users] → [{id}]
// /api/users/me    → [api] → [users] → [me]
// /api/posts       → [api] → [posts]

Redis 키 설계

Redis에서 user:1001:profile, user:1001:settings 같은 키 패턴은 Trie적 사고방식입니다. SCAN 명령으로 접두사 기반 검색을 할 때 유사한 원리가 작동합니다.

라우팅 테이블

네트워크 라우터의 IP 라우팅 테이블은 비트 단위 Trie로 구현됩니다. 가장 긴 접두사 매칭(Longest Prefix Match)으로 패킷의 목적지를 결정합니다.

검색 엔진

검색 엔진의 자동 완성(typeahead) 기능은 Trie 또는 그 변형(Ternary Search Tree)을 기반으로 합니다.

주의할 점

메모리 사용량을 과소평가하는 실수

Trie는 각 노드가 알파벳 크기만큼의 자식 포인터를 가집니다. 영소문자만이면 노드당 26개, 유니코드면 수만 개의 포인터가 필요합니다. 문자열 수가 적으면 HashMap 기반 Trie나 다른 자료구조가 더 효율적일 수 있습니다.

단어의 끝 표시(isEnd)를 빠뜨리는 실수

"app"을 삽입한 뒤 "apple"을 삽입하면, "app" 경로는 존재하지만 isEnd가 없으면 "app"이 존재하는 단어인지 알 수 없습니다.

정리

Trie 는 문자열의 각 문자를 간선으로 표현하는 트리 자료구조입니다
검색, 삽입, 삭제 모두 O(L) 로 문자열 길이에만 비례합니다
접두사 검색 과 자동 완성 에 해시맵보다 훨씬 유리합니다
메모리가 단점이지만, HashMap 기반 노드나 압축 Trie로 개선할 수 있습니다
Spring URL 매칭, IP 라우팅, 검색 자동 완성 등 실무 곳곳에서 활용됩니다