트라이 변형 — Compressed Trie와 Radix Tree

트라이(Trie)가 문자열 검색에 좋다는 것은 아는데, 노드가 너무 많아지는 문제는 어떻게 해결할까요?

일반 Trie 복습

Trie(Prefix Tree)는 문자열을 문자 단위로 트리에 저장하는 자료구조입니다.

PLAINTEXT

"cat", "car", "card", "care"를 저장한 Trie:

        (root)
         |
         c
         |
         a
        / \
       t   r
          / \
         d   e

문제는 다음과 같습니다.

분기가 없는 긴 경로가 생기면 노드 낭비 가 심합니다
"internationalization" 같은 단어 하나에 노드가 20개 필요합니다

Compressed Trie (Radix Tree)란

Compressed Trie는 분기가 없는 경로를 하나의 노드로 압축 한 트라이입니다. Radix Tree라고도 합니다.

일반 Trie vs Compressed Trie

PLAINTEXT

일반 Trie:                    Compressed Trie (Radix Tree):

    (root)                         (root)
     |                              |
     c                             "ca"
     |                            /    \
     a                          "t"   "r"
    / \                               / \
   t   r                            "d"  "e"
      / \
     d   e

"c" → "a" 경로에 분기가 없으므로 "ca" 하나로 합칩니다.

더 극적인 예시

PLAINTEXT

"romane", "romanus", "romulus", "rubens", "ruber"

일반 Trie: 노드 약 30개
Radix Tree: 노드 약 10개

         (root)
         /    \
       "rom"  "rub"
       / \      / \
    "an" "ulus" "ens" "er"
    / \
  "e"  "us"

Radix Tree 구현

JAVA

class RadixNode {
    String label;          // 간선에 대응하는 문자열
    Map<Character, RadixNode> children;
    boolean isEnd;         // 단어의 끝인지
    Object value;          // 저장할 값 (필요 시)

    RadixNode(String label) {
        this.label = label;
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}

public class RadixTree {
    private RadixNode root = new RadixNode("");

    public void insert(String key) {
        RadixNode current = root;
        int i = 0;

        while (i < key.length()) {
            char c = key.charAt(i);
            RadixNode child = current.children.get(c);

            if (child == null) {
                // 새로운 간선 생성
                RadixNode newNode = new RadixNode(key.substring(i));
                newNode.isEnd = true;
                current.children.put(c, newNode);
                return;
            }

            // 공통 접두사 길이 계산
            String label = child.label;
            int commonLen = commonPrefixLength(key.substring(i), label);

            if (commonLen == label.length()) {
                // 간선 라벨이 완전히 매칭 → 다음 노드로
                i += commonLen;
                current = child;
            } else {
                // 간선을 분할해야 함
                splitEdge(current, child, c, key.substring(i), commonLen);
                return;
            }
        }
        current.isEnd = true;
    }

    private int commonPrefixLength(String a, String b) {
        int len = Math.min(a.length(), b.length());
        for (int i = 0; i < len; i++) {
            if (a.charAt(i) != b.charAt(i)) return i;
        }
        return len;
    }

    private void splitEdge(RadixNode parent, RadixNode child,
                           char key, String remaining, int commonLen) {
        // 공통 부분으로 중간 노드 생성
        RadixNode mid = new RadixNode(child.label.substring(0, commonLen));
        parent.children.put(key, mid);

        // 기존 자식을 중간 노드 아래로 이동
        child.label = child.label.substring(commonLen);
        mid.children.put(child.label.charAt(0), child);

        // 남은 부분으로 새 노드 생성
        if (commonLen < remaining.length()) {
            String rest = remaining.substring(commonLen);
            RadixNode newNode = new RadixNode(rest);
            newNode.isEnd = true;
            mid.children.put(rest.charAt(0), newNode);
        } else {
            mid.isEnd = true;
        }
    }

    public boolean search(String key) {
        RadixNode current = root;
        int i = 0;

        while (i < key.length()) {
            char c = key.charAt(i);
            RadixNode child = current.children.get(c);
            if (child == null) return false;

            String label = child.label;
            if (!key.substring(i).startsWith(label)) return false;

            i += label.length();
            current = child;
        }
        return current.isEnd;
    }
}

Patricia Trie

Patricia Trie(Practical Algorithm To Retrieve Information Coded In Alphanumeric)는 비트 단위로 분기하는 Radix Tree의 특수한 형태입니다.

일반 Radix Tree와의 차이

일반 Radix Tree: 문자 단위 분기
Patricia Trie: ** 비트 단위** 분기

PLAINTEXT

키: "ABC" = 01000001 01000010 01000011
키: "ABD" = 01000001 01000010 01000100

22번째 비트에서 처음 달라짐 → 22번째 비트에서 분기

비트 단위로 분기하므로 더 세밀한 압축이 가능하고, IP 주소 같은 이진 데이터에 특히 유용합니다.

Linux 라우팅 테이블

Linux 커널은 IP 라우팅 테이블을 Radix Tree (구체적으로는 LC-Trie) 로 구현합니다.

IP 주소와 접두사 매칭

라우팅은 Longest Prefix Match(LPM), 가장 긴 접두사가 매칭되는 경로를 찾는 문제입니다.

PLAINTEXT

라우팅 테이블:
192.168.0.0/16   → Gateway A
192.168.1.0/24   → Gateway B
192.168.1.128/25 → Gateway C

목적지: 192.168.1.200
→ 세 규칙 모두 매칭되지만, 가장 긴 접두사인 /25가 선택됨
→ Gateway C로 라우팅

Radix Tree는 공통 접두사를 공유하므로, 트리를 타고 내려가면서 자연스럽게 LPM을 수행합니다.

PLAINTEXT

            (root)
              |
          192.168
           /    \
         0.0/16  1
        (GW-A)  / \
           0/24  128/25
          (GW-B)  (GW-C)

Spring URL 패턴 매칭

Spring MVC의 PathPatternParser는 내부적으로 트라이와 유사한 구조를 사용하여 URL을 매칭합니다.

예시

JAVA

@RestController
@RequestMapping("/api")
public class UserController {
    @GetMapping("/users")          // /api/users
    public List<User> list() { ... }

    @GetMapping("/users/{id}")     // /api/users/{id}
    public User get(@PathVariable Long id) { ... }

    @GetMapping("/users/{id}/orders")  // /api/users/{id}/orders
    public List<Order> orders(@PathVariable Long id) { ... }
}

내부적으로 다음과 같은 트리 구조가 만들어집니다.

PLAINTEXT

    /api
      |
    /users
     / \
   (끝)  /{id}
          / \
        (끝) /orders
              (끝)

이 구조 덕분에 /api 접두사는 한 번만 비교하면 됩니다. 등록된 핸들러가 수백 개여도 효율적으로 매칭할 수 있습니다.

Spring 6의 PathPatternParser

JAVA

// Spring 6에서 PathPatternParser가 기본 설정
// AntPathMatcher보다 트라이 기반으로 더 효율적

@Configuration
public class WebConfig implements WebMvcConfigurer {
    @Override
    public void configurePathMatch(PathMatchConfigurer configurer) {
        // Spring 6부터 기본적으로 PathPatternParser 사용
        // 내부적으로 경로 세그먼트를 트리 구조로 관리
    }
}

Redis의 접두사 기반 키 관리

Redis에서 키를 계층적으로 관리할 때도 트라이의 원리가 적용됩니다.

BASH

# 관례적으로 콜론으로 계층 구분
SET user:1001:name "Alice"
SET user:1001:email "alice@example.com"
SET user:1002:name "Bob"

# SCAN 명령으로 접두사 기반 검색
SCAN 0 MATCH user:1001:*

내부적으로 Redis의 키 저장은 해시 테이블이지만, 키 설계 자체가 트라이의 계층 구조를 모방합니다.

Trie vs Radix Tree vs HashMap 비교

특성	Trie	Radix Tree	HashMap
접두사 검색	O(m)	O(m)	O(n) 전체 스캔
정확 매칭	O(m)	O(m)	O(1) 평균
메모리	높음	중간	낮음
정렬 순회	자연스럽게 지원	지원	불가
LPM	지원	최적	불가

m은 키의 길이

실무에서의 선택 기준

**정확한 키 매칭만 필요 **: HashMap이 최선
** 접두사 검색이 필요 **: Trie 또는 Radix Tree
**IP 주소, URL 매칭 **: Radix Tree
** 자동완성 **: Trie (모든 접두사 매칭 결과를 쉽게 순회)
** 메모리가 중요 **: Radix Tree (Trie보다 노드가 적음)

정리

Compressed Trie (Radix Tree) 는 분기 없는 경로를 압축하여 Trie의 메모리 문제를 해결합니다.
Patricia Trie 는 비트 단위로 분기하는 Radix Tree로, IP 주소 처리에 적합합니다.
Linux 라우팅 테이블 은 Radix Tree로 Longest Prefix Match를 효율적으로 수행합니다.
Spring의 URL 패턴 매칭 도 트라이와 유사한 구조로 공통 접두사를 효율적으로 처리합니다.
접두사 검색이 필요하면 Trie/Radix Tree, 정확한 매칭만 필요하면 HashMap이 적합합니다.