트라이: 철자를 쓰는 트리

"해시맵은 'pippa' 가 네 집합에 있는지 알려줘. 트라이는 'pip' 으로 시작하는 모든 단어를 알려줘 — 그 추가 능력 하나가 네가 써본 모든 자동완성을 굴려."

글자로 지은 트리

트라이 (접두사 트리) 는 문자열을 그 문자로 저장해: 각 엣지가 문자 하나고, 루트에서의 각 경로가 접두사를 철자해. 접두사를 공유하는 단어는 갈라지기 전까지 같은 경로를 공유해 — "cat", "car", "card" 가 다 c→a→ 를 함께 걷고, 그다음 갈려. 노드는 진짜 단어의 끝으로 표시돼서 "car" (단어) 를 "ca" (단어로 가는 길의 접두사일 뿐) 에서 구별할 수 있어.

비용이 쓸모 있게 달라

삽입이랑 조회는 문자당 엣지 하나를 걸어서, O(L) 야 L 이 키 길이. 그리고 결정적으로, 그게 트라이가 단어를 몇 개 들고 있든 무관해. 단어 열 개 트라이랑 천만 개 트라이가 둘 다 5글자 단어를 5 단계에 조회해. (해시맵도 여기서 빠르지만, 그 비용은 키 전체를 해싱하는 데 달렸어; 트라이는 키 길이에만 달렸어.)

킬러 기능: 접두사 쿼리

해시맵이 그냥 못 하는 거: "pre 로 시작하는 모든 키 줘" 에 답하기. 트라이에선, pre 끝의 노드로 걸어가 (O(접두사 길이)), 그 아래 서브트리 안 모든 게 그 접두사를 가진 단어야 — O(결과 수) 에 모아. 정확히 자동완성 (타이핑하면서 완성 제안), 맞춤법 검사, 사전 조회, IP 라우팅 (라우터가 주소 비트로 최장 접두사 매칭) 을 굴리는 거야. 쿼리가 접두사에 관한 거면, 트라이가 그 구조야, BST 가 쿼리가 순서에 관한 거일 때 그 구조인 것처럼.

트라이는 문자열을 문자 경로로 저장하며 접두사를 공유해. 조회/삽입이 O(키 길이), 키 수와 무관. 고유 능력은 접두사 쿼리 — 'X 로 시작하는 모든 단어' — 로 해시맵이 못 해. 자동완성, 맞춤법 검사, 라우팅에 써.

거래

트라이는 공짜가 아니야. 각 노드가 오버헤드 (자식 문자 맵) 를 들어서, 무관한 문자열 작은 집합엔 트라이가 평범한 해시 셋보다 메모리를 더 쓸 수 있어 — 절약은 많은 키가 접두사를 공유할 때만 실현돼. 그리고 접두사 필요 없는 순수 정확-멤버십엔 해시 셋이 여전히 이겨. 늘 그렇듯: 트라이는 쿼리 모양이 "접두사" 일 때 정확히 자리를 벌고, 아닐 땐 과잉이야. 맞는 구조, 맞는 쿼리.

피파의 고백

난 해시 셋이랑 모든 키에 key.startswith(prefix) 를 확인하는 반복문으로 자동완성을 지으려 했어 — 키 입력당 O(n), 큰 사전에서 버벅였어. 아빠가 트라이를 그리니 버벅임이 사라졌어: 접두사 노드로 한 번 걷고, 서브트리를 읽어. 또 한 번 구조를 재구성했어 — 해시 셋이 틀린 질문에 답하고 있었어. '이 정확한 단어 있나?' 엔 환상적이고 '이걸 뭐가 잇냐?' 엔 무력해. 쿼리 모양이 구조를 골라.

Code

삽입, 검색, 접두사 쿼리 있는 트라이·python

class Trie:
    def __init__(self):
        self.root = {}                  # 중첩 dict; '$' 가 단어 끝 표시

    def insert(self, word):             # O(len(word))
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # 문자당 엣지 하나 걷기/생성
        node["$"] = True                # 진짜 단어가 여기서 끝남 표시

    def search(self, word):             # O(len(word)) 정확-단어 조회
        node = self.root
        for ch in word:
            if ch not in node: return False
            node = node[ch]
        return "$" in node

    def starts_with(self, prefix):      # 해시맵에 없는 킬러 기능
        node = self.root
        for ch in prefix:
            if ch not in node: return []
            node = node[ch]
        words = []                      # 이 서브트리 안 모든 단어 모으기
        def collect(n, path):
            if "$" in n: words.append(prefix + path)
            for ch, child in n.items():
                if ch != "$": collect(child, path + ch)
        collect(node, "")
        return words

t = Trie()
for w in ["cat", "car", "card", "dog"]:
    t.insert(w)
print(t.search("car"))          # True
print(t.search("ca"))           # False — 접두사지 저장된 단어 아님
print(t.starts_with("car"))     # ['car', 'card'] — 접두사 쿼리, 트라이의 선물

Exercise

'to', 'tea', 'ted', 'ten', 'in', 'inn' 을 트라이에 삽입하고 공유 구조를 스케치해. 'tea', 'ted', 'ten' 이 공유하는 접두사 경로는? 그다음 'te 로 시작하는 모든 단어' 답하기가 왜 O(총 저장 단어) 가 아니라 O(접두사 + 결과) 인지 설명해.

Hint

'tea','ted','ten' 은 t→e 경로를 공유하고, 세 번째 글자에서 갈려. 'te 로 시작하는 모든 단어' 는 'te' 노드까지 2글자 경로를 걷고, 그 서브트리만 탐색해 — 'to', 'in', 'inn' 은 절대 안 건드려, 그래서 비용이 전체 트라이가 아니라 접두사랑 매치에 달려.

글자로 지은 트리

비용이 쓸모 있게 달라

킬러 기능: 접두사 쿼리

거래

피파의 고백

Code

External links

Exercise

Progress

댓글 0