컴퓨터공학 300 주제 시리즈의 052번째 글이다. 전체 지도는 여기.

한 줄 요약

트라이(trie)는 문자열을 한 글자씩 간선으로 내려가며 저장하는 트리로, 공통 접두사를 한 번만 저장하고, 키 길이 L 에 대해 O(L) 에 찾으며, 자동완성과 최장 접두사 일치처럼 “접두사”를 묻는 질문에 특히 강하다.

왜 필요한가

해시 테이블은 “kubectl 이 있나?”에는 빠르게 답한다. 그런데 “kube 로 시작하는 단어 전부”를 물으면 모든 키를 훑어야 한다. 정렬된 배열이나 BST 는 접두사 범위를 찾을 수 있지만, 비교할 때마다 문자열 전체를 다시 비교한다.

트라이는 아예 문자열의 구조를 자료구조로 만든다. 같은 접두사를 가진 단어들은 같은 경로를 공유한다. 그래서 접두사 하나를 따라 내려가면, 그 아래 서브트리 전체가 곧 그 접두사로 시작하는 단어 집합이다. 검색창 자동완성, 맞춤법 검사기, IP 라우팅 테이블, 웹 서버의 URL 라우터까지 이 아이디어가 쓰인다. 이름은 retrieval 에서 따왔고, Fredkin 이 1960년 논문 “Trie Memory” 에서 이 용어를 썼다.

핵심 개념

구조

각 노드는 “다음 글자 → 자식 노드” 사상과, “여기서 끝나는 단어가 있다”는 표시를 가진다. NIST 알고리즘·자료구조 사전은 트라이를 “모든 공통 접두사마다 노드가 하나씩 있는, 문자열을 저장하는 트리”로 정의한다(NIST DADS — trie).

단어: kube, kubectl, kubelet, kubeadm, helm, help

            (root)
           /      \
          k        h
          |        |
          u        e
          |        |
          b        l
          |       / \
          e*     m*  p*
        / | \
       a  c  l
       |  |  |
       d  t  e
       |  |  |
       m* l* t*

  * = 단어 끝 표시

kube 는 kubectl 의 접두사이면서 그 자체로도 단어라서, 중간 노드에 끝 표시가 붙는다. 끝 표시 없이 “잎인가”로 판단하면 이런 경우를 놓친다.

연산 비용

키 길이를 L, 저장된 단어 수를 n 이라 하자.

연산 트라이 해시 테이블 균형 BST
정확히 찾기 O(L) 평균 O(L) (해시 계산) O(L log n) (비교마다 최대 L)
삽입 O(L) 평균 O(L) O(L log n)
접두사로 시작하는 k 개 O(L + 출력 크기) O(전체) O(L log n + 출력 크기)
최장 접두사 일치 O(L) 길이별로 여러 번 조회 어렵다
사전순 순회 자식을 순서대로 DFS 불가 중위 순회

트라이의 비용은 n 과 무관하다. 단어가 백 개든 백만 개든 kubectl 을 찾는 데 7번 내려가면 끝이다.

메모리 문제와 자식 표현

트라이의 약점은 메모리다. 노드가 글자 하나마다 생기고, 각 노드가 자식 표를 들고 있다.

자식 표현 자식 찾기 메모리
고정 배열 (예: 26칸, 256칸) O(1) 노드마다 큰 배열, 대부분 비어 낭비
해시 맵 (이 글의 예제) 평균 O(1) 중간
정렬 리스트 O(log σ) 작음

σ 는 알파벳 크기다. 그래서 실무에서는 다음과 같은 압축 변형을 쓴다.

  • 기수 트리(radix tree, 패트리샤 트리): 자식이 하나뿐인 노드의 사슬을 간선 하나로 합친다. 위 그림의 k-u-b-e 가 간선 하나 “kube” 가 된다. 노드 수가 단어 수에 비례하게 줄어든다.
  • LC-trie (level compression): 꽉 찬 아래층 여러 단계를 한 노드의 큰 배열로 합쳐 높이를 줄인다. 리눅스 커널의 IPv4 라우팅 테이블이 이 구조를 쓴다.

최장 접두사 일치(LPM)

인터넷 라우팅은 목적지 주소와 가장 길게 일치하는 경로를 고른다. RFC 4632(CIDR)는 인터넷의 전달이 최장 일치를 기준으로 이루어진다고 규정한다(RFC 4632). 예를 들어 10.0.0.0/8 과 10.20.3.0/24 가 모두 있으면, 10.20.3.77 은 더 긴 /24 를 따른다.

IP 주소를 비트 문자열로 보면 이것은 정확히 트라이 문제다. 주소 비트를 따라 내려가며, 지나친 노드 중 경로 정보가 있는 가장 깊은 노드를 기억하면 된다. 리눅스 커널의 fib_trie 문서는 일치를 못 찾으면 접두사 길이를 한 단계씩 줄이며 트라이를 거슬러 올라가 최장 일치 접두사를 찾는다고 설명한다(Linux Kernel — LC-trie implementation notes).

직접 해 보기

해시 맵 자식을 쓰는 트라이로 자동완성을 만들고, 비트 트라이로 라우팅 테이블의 최장 접두사 일치를 흉내 낸다. 예제의 주소는 설명용으로 지어낸 사설 대역이다.

class TrieNode:
    __slots__ = ("kids", "end")
    def __init__(self):
        self.kids = {}        # 문자 → 자식 노드
        self.end = False      # 여기서 끝나는 단어가 있는가

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.nodes = 1

    def insert(self, word):
        n = self.root
        for ch in word:
            if ch not in n.kids:
                n.kids[ch] = TrieNode()
                self.nodes += 1
            n = n.kids[ch]
        n.end = True

    def _walk(self, s):
        n = self.root
        for ch in s:
            n = n.kids.get(ch)
            if n is None:
                return None
        return n

    def contains(self, word):
        n = self._walk(word)
        return n is not None and n.end

    def starts_with(self, prefix, limit=10):
        n, out = self._walk(prefix), []
        def dfs(node, path):
            if len(out) >= limit:
                return
            if node.end:
                out.append(prefix + path)
            for ch in sorted(node.kids):
                dfs(node.kids[ch], path + ch)
        if n:
            dfs(n, "")
        return out

t = Trie()
words = ["kube", "kubectl", "kubelet", "kubeadm", "kustomize", "helm", "help"]
for w in words:
    t.insert(w)
print("노드 수:", t.nodes, " 글자 수 합:", sum(map(len, words)))
print("kube 있나?", t.contains("kube"), " kub 있나?", t.contains("kub"))
print("'kube' 자동완성:", t.starts_with("kube"))
print("'hel' 자동완성:", t.starts_with("hel"))

# 최장 접두사 일치(LPM): IPv4 라우팅을 비트 트라이로
import ipaddress
class BitTrie:
    def __init__(self):
        self.root = {}
    def add(self, cidr, nexthop):
        net = ipaddress.ip_network(cidr)
        bits = format(int(net.network_address), "032b")[:net.prefixlen]
        n = self.root
        for b in bits:
            n = n.setdefault(b, {})
        n["hop"] = nexthop
    def lookup(self, ip):
        bits = format(int(ipaddress.ip_address(ip)), "032b")
        n, best = self.root, self.root.get("hop")
        for b in bits:
            n = n.get(b)
            if n is None:
                break
            best = n.get("hop", best)       # 더 긴 접두사를 만나면 갱신
        return best

rt = BitTrie()
rt.add("0.0.0.0/0", "기본 게이트웨이")
rt.add("10.0.0.0/8", "사설망 전체")
rt.add("10.20.0.0/16", "지점 A")
rt.add("10.20.3.0/24", "지점 A 3층")
for ip in ["8.8.8.8", "10.1.2.3", "10.20.9.9", "10.20.3.77"]:
    print(f"{ip:>12} → {rt.lookup(ip)}")

노드 수: 26  글자 수 합: 42
kube 있나? True  kub 있나? False
'kube' 자동완성: ['kube', 'kubeadm', 'kubectl', 'kubelet']
'hel' 자동완성: ['helm', 'help']
     8.8.8.8 → 기본 게이트웨이
    10.1.2.3 → 사설망 전체
   10.20.9.9 → 지점 A
  10.20.3.77 → 지점 A 3층

7개 단어의 글자 수 합은 42 인데 노드는 루트 포함 26개다. 공통 접두사 ku, kube, hel 이 한 번만 저장되었다. kub 는 경로는 있지만 끝 표시가 없으므로 단어가 아니다. 자식을 정렬된 순서로 방문했기 때문에 자동완성 결과가 사전순으로 나왔다. 라우팅 쪽은 같은 10.20.x.x 라도 /24 에 속하면 더 구체적인 경로를 따른다.

현업에서는

  • 라우팅과 방화벽. 커널 라우팅 테이블, 그리고 CIDR 목록으로 허용·차단을 결정하는 방화벽과 네트워크 정책 구현이 접두사 트리 계열을 쓴다. 규칙이 수만 개여도 조회 비용은 주소 비트 수에 묶인다.
  • HTTP 라우터. 웹 프레임워크의 URL 라우터 중에는 경로 조각을 기준으로 한 기수 트리로 /api/v1/users/:id 같은 패턴을 매칭하는 것들이 있다. 이렇게 하면 라우트 수가 늘어도 매칭 시간이 거의 늘지 않는다.
  • 자동완성과 검색. 검색창 자동완성, IDE 의 심볼 완성, 셸 명령 완성이 접두사 질의다. 큰 사전에서는 메모리 때문에 압축 트라이나 FST(유한 상태 변환기) 같은 더 압축된 구조를 쓴다.
  • 메모리 주의. 파이썬에서 객체 노드로 만든 트라이는 문자 하나에 수십~수백 바이트를 쓴다. 단어 수백만 개를 담으려면 압축 변형이나 정렬 배열 + 이진 탐색이 더 나을 수 있다. 측정해 보고 고른다.

확인 문제

  1. 빈 트라이에 “tea”, “ten”, “to”, “inn” 을 넣으면 루트를 포함해 노드가 몇 개인가?
  2. 트라이에서 단어 끝을 “잎 노드인가”로 판단하면 어떤 경우에 틀리는가?
  3. 해시 테이블보다 트라이가 유리한 질의 두 가지는?
  4. 라우팅 테이블에 10.0.0.0/8 과 10.20.0.0/16 이 있을 때 10.21.0.1 은 어느 경로를 따르는가?
  5. 기수 트리(radix tree)는 기본 트라이의 어떤 낭비를 줄이는가?

풀이

  1. 루트, t, te, tea, ten, to, i, in, inn 으로 9개.
  2. 다른 단어의 접두사인 단어(예: “kube” 와 “kubectl”)는 중간 노드에서 끝나므로 잎이 아니다. 별도의 끝 표시가 필요하다.
  3. 접두사로 시작하는 키 나열(자동완성), 최장 접두사 일치. (사전순 순회도 해당)
  4. 10.0.0.0/8. 10.21 은 10.20.0.0/16 범위 밖이다.
  5. 자식이 하나뿐인 노드가 길게 이어지는 사슬을 간선 하나로 합쳐 노드 수와 포인터 추적을 줄인다.

더 읽을거리 (References)