Oh My Algorithm
Algorithm Guidecomplexity: O(m) (문자열 길이)

트라이 (Trie)

문자열을 글자 단위로 가지에 저장하는 접두사 트리입니다. 공통 접두사를 공유해 자동완성·사전·접두사 검색을 문자열 길이 O(m)에 처리합니다.

01트라이 (Trie)

트라이 시작. 문자열을 글자 단위로 가지에 저장하고, 공통 접두사는 같은 길을 함께 씁니다.

insert('cat') · 루트에서 c → a → t로 새 길을 만들고, 마지막 t를 '단어 끝'으로 표시합니다.

insert('car') · c·a는 이미 있어 공유하고, r만 새로 추가합니다 — 접두사를 함께 쓰는 게 핵심입니다.

insert('dog') · 첫 글자부터 다르므로 d → o → g로 완전히 새로운 가지를 만듭니다.

search('car') · 루트에서 c → a → r로 글자를 따라가고, r이 '단어 끝'이므로 찾았습니다.

공통 접두사를 공유해 메모리를 아끼고, 탐색은 단어 길이 O(m)에 끝납니다. 자동완성의 기반입니다.

•
1 / 6

02 쉽게 이해하기

For Everyone
🔑핵심 동작

문자를 간선으로 삼아 접두사가 같은 단어들이 같은 경로를 공유합니다. 찾는 시간이 사전 크기가 아니라 단어 길이에 비례합니다.

💡쉽게 말하면

문자열을 글자 단위로 가지에 저장해 공통 접두사를 함께 쓰는 트리예요.

단어 길이 O(m)에 찾고, 특정 접두사로 시작하는 단어들을 빠르게 모읍니다.

📍어디에 쓰나
  • –검색어 자동완성
  • –사전·맞춤법 검사
  • –IP 라우팅

03 파이썬 구현 코드

트라이 (Trie)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

04 자주 묻는 질문

FAQ
트라이 (Trie)란 무엇인가요?+

문자열을 글자 단위로 가지에 저장하는 접두사 트리입니다. 공통 접두사를 공유해 자동완성·사전·접두사 검색을 문자열 길이 O(m)에 처리합니다.

트라이 (Trie)의 시간복잡도는 어떻게 되나요?+

트라이 (Trie)의 시간복잡도는 O(m) (문자열 길이) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

트라이 (Trie)은(는) 어디에 사용하나요?+

검색어 자동완성, 사전·맞춤법 검사, IP 라우팅.

트라이 (Trie)를 쉽게 비유하면?+

문자를 간선으로 삼아 접두사가 같은 단어들이 같은 경로를 공유합니다. 찾는 시간이 사전 크기가 아니라 단어 길이에 비례합니다.

→ 트리 전체 보기Related
🌳트리 순회 (Tree Traversal)
O(n)
🌳AVL 트리 (AVL Tree)
O(log n)
🌳세그먼트 트리 (Segment Tree)
질의·갱신 O(log n)