트라이(접두사 트리)

Q: 트라이의 시간 복잡도는 어떻게 되나요?

삽입, 검색, 접두사 질의는 모두 `O(m)`으로 실행되며, 여기서 `m`은 단어 또는 접두사의 길이이고 저장된 단어 수와는 무관합니다. 트레이드오프는 메모리입니다: 공유 접두사는 한 번만 저장되지만 트라이는 많은 공간을 사용할 수 있습니다.

Q: 트라이와 해시 테이블의 차이는 무엇인가요?

해시 테이블은 완전한 키를 평균 `O(1)`에 조회하지만 접두사 질의에는 답할 수 없습니다. 트라이는 조회당 약간 더 느리지만 접두사 검색, 정렬된 순회, 자동완성을 자연스럽게 지원합니다 - 그것이 이러한 용도에서 선호되는 이유입니다.

Q: 이진 탐색 트리 대신 언제 트라이를 사용해야 하나요?

키가 문자열이고 접두사 검색이 필요할 때 트라이를 사용하세요: 키 길이에 대해 연산당 `O(m)`으로 동작하는 반면, 균형 이진 탐색 트리는 각 비교가 문자열을 훑고 그런 비교가 `log n`번 있으므로 `O(m log n)`이 듭니다. 키가 문자열 형태가 아니거나 메모리 오버헤드가 접두사 속도보다 더 중요할 때는 이진 탐색 트리가 더 나은 선택입니다.

마지막 업데이트 2026년 7월 1일

트라이("트라이"로 발음), 즉 접두사 트리는 문자열 집합을 그 문자들로 저장합니다. 각 간선에는 하나의 문자가 레이블로 붙고, 루트에서 시작하는 경로가 하나의 접두사를 이룹니다. 접두사를 공유하는 단어들은 같은 노드를 공유하므로 "car", "card", "care"는 모두 c-a-r 경로를 재사용합니다. 위의 재생 버튼을 눌러 단어가 한 글자씩 삽입되고 서로 다른 지점에서만 분기하는 모습을 확인하세요.

검색은 문자당 하나의 노드를 따라가므로, 길이 m인 단어를 검색하는 데는 트라이가 담고 있는 단어 수와 무관하게 O(m)이 걸립니다. 그래서 트라이는 자동완성, 맞춤법 검사, 접두사 검색에 이상적입니다.

시간 및 공간 복잡도

연산	복잡도	비고
삽입	O(m)	m = 단어의 길이
검색	O(m)	문자당 한 단계
접두사 질의	O(m)	접두사 노드까지 따라감
공간	O(total chars)	공유되는 접두사는 한 번만 저장됨

단계별 (삽입)

단계	무슨 일이 일어나는가
1	루트 노드에서 시작한다.
2	단어의 각 문자에 대해 일치하는 자식 간선을 찾는다.
3	존재하면 그것을 따라간다(공유 접두사를 재사용).
4	없으면 그 문자를 위한 새 자식 노드를 만든다.
5	마지막 문자 뒤에 그 노드를 단어의 끝으로 표시한다.

예제 따라가기

빈 트라이에 ["car", "card", "care"]를 삽입:

단계	구조	동작
`car` 삽입	`root → c → a → r✓`	일치하는 자식이 없으므로 `c`, `a`, `r`를 만들고 `r`를 단어의 끝으로 표시한다.
`card` 삽입	`root → c → a → r✓ → d✓`	기존 `c-a-r` 경로를 재사용한 뒤 새 자식 `d`를 하나 만들어 단어의 끝으로 표시한다.
`care` 삽입	`root → c → a → r✓ → {d✓, e✓}`	`c-a-r`를 재사용하고 `r`에서 새 자식 `e`로 분기한 뒤 `e`를 단어의 끝으로 표시한다.
`care` 검색	`root → c → a → r → e✓`	`c`, `a`, `r`, `e`를 따라간다. 마지막 노드가 단어의 끝으로 표시되어 있으므로 `care`가 존재한다.
`ca` 검색	`root → c → a`	경로는 존재하지만 `a`가 단어의 끝으로 표시되어 있지 않으므로 `ca`는 접두사일 뿐 저장된 단어는 아니다.

트라이를 언제 사용하는가

사용할 때	피할 때
문자열 집합에 대해 접두사 질의나 자동완성이 필요할 때.	완전한 키 검색만 필요할 때 - 해시 테이블이 더 빠르고 가볍다.
저장된 많은 단어가 공통 접두사를 공유해 노드가 재사용될 때.	키가 길고 거의 겹치지 않아 문자당 노드를 낭비할 때.
순회를 통해 키를 정렬된 순서로 반환하고 싶을 때.	메모리가 빠듯할 때 - 노드당 자식 포인터가 상당한 오버헤드를 더한다.
검색 비용이 데이터셋 크기가 아니라 키 길이에 의존해야 할 때.	알파벳이 거대하고(예: 전체 유니코드) 자식을 밀집 저장할 때.

Trie (Prefix Tree) 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Trie (Prefix Tree) 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Trie (Prefix Tree) 코드Python
1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_word = False5
6
7class Trie:8    def __init__(self):9        self.root = TrieNode()10
11    def insert(self, word):12        node = self.root13        for ch in word:14            node = node.children.setdefault(ch, TrieNode())15        node.is_word = True16
17    def search(self, word):18        node = self._walk(word)19        return node is not None and node.is_word20
21    def starts_with(self, prefix):22        return self._walk(prefix) is not None23
24    def _walk(self, s):25        node = self.root26        for ch in s:27            if ch not in node.children:28                return None29            node = node.children[ch]30        return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35    trie.insert(word)36
37print("search(card):     ", trie.search("card"))38print("search(ca):       ", trie.search("ca"))39print("starts_with(ca):  ", trie.starts_with("ca"))40print("starts_with(do):  ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Trie (Prefix Tree) 코드JavaScript
1class TrieNode {2    constructor() {3        this.children = {};4        this.isEnd = false;5    }6}7
8class Trie {9    constructor() {10        this.root = new TrieNode();11    }12
13    insert(word) {14        let node = this.root;15        for (const ch of word) {16            if (!node.children[ch]) node.children[ch] = new TrieNode();17            node = node.children[ch];18        }19        node.isEnd = true;20    }21
22    // Walk the prefix; null when a character is missing23    findNode(prefix) {24        let node = this.root;25        for (const ch of prefix) {26            node = node.children[ch];27            if (!node) return null;28        }29        return node;30    }31
32    search(word) {33        const node = this.findNode(word);34        return node !== null && node.isEnd;35    }36
37    startsWith(prefix) {38        return this.findNode(prefix) !== null;39    }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Trie (Prefix Tree) 코드Java
1public class Main {2    static class Node {3        Node[] children = new Node[26];4        boolean isWord;5    }6
7    static Node root = new Node();8
9    static void insert(String word) {10        Node cur = root;11        for (char c : word.toCharArray()) {12            int i = c - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isWord = true;17    }18
19    // Follow the path for s; null means no word has this prefix20    static Node walk(String s) {21        Node cur = root;22        for (char c : s.toCharArray()) {23            cur = cur.children[c - 'a'];24            if (cur == null) return null;25        }26        return cur;27    }28
29    static boolean search(String word) {30        Node node = walk(word);31        return node != null && node.isWord;32    }33
34    static boolean startsWith(String prefix) {35        return walk(prefix) != null;36    }37
38    public static void main(String[] args) {39        insert("code");40        insert("coder");41        insert("cool");42        System.out.println("search code: " + search("code"));43        System.out.println("search cod: " + search("cod"));44        System.out.println("startsWith cod: " + startsWith("cod"));45        System.out.println("startsWith cat: " + startsWith("cat"));46    }47}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Trie (Prefix Tree) 코드C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6    std::unordered_map<char, TrieNode*> children;7    bool isEnd = false;8};9
10struct Trie {11    TrieNode* root = new TrieNode();12
13    void insert(const std::string& word) {14        TrieNode* node = root;15        for (char c : word) {16            if (!node->children.count(c)) node->children[c] = new TrieNode();17            node = node->children[c];18        }19        node->isEnd = true;20    }21
22    // Follow the path for s; nullptr if a link is missing23    TrieNode* walk(const std::string& s) const {24        TrieNode* node = root;25        for (char c : s) {26            auto it = node->children.find(c);27            if (it == node->children.end()) return nullptr;28            node = it->second;29        }30        return node;31    }32
33    bool search(const std::string& word) const {34        TrieNode* node = walk(word);35        return node != nullptr && node->isEnd;36    }37
38    bool startsWith(const std::string& prefix) const {39        return walk(prefix) != nullptr;40    }41};42
43int main() {44    Trie trie;45    for (const std::string& word : {"car", "card", "care", "dog"}) {46        trie.insert(word);47    }48    std::cout << std::boolalpha;49    std::cout << "search(card): " << trie.search("card") << "\n";50    std::cout << "search(ca): " << trie.search("ca") << "\n";51    std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52    std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53    return 0;54}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Trie (Prefix Tree) 코드C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6    struct TrieNode* children[26];7    bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11    return calloc(1, sizeof(TrieNode));  // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15    for (; *word; word++) {16        int i = *word - 'a';17        if (root->children[i] == NULL) root->children[i] = newNode();18        root = root->children[i];19    }20    root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25    for (; *s; s++) {26        root = root->children[*s - 'a'];27        if (root == NULL) return NULL;28    }29    return root;30}31
32bool search(TrieNode* root, const char* word) {33    TrieNode* node = walk(root, word);34    return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38    return walk(root, prefix) != NULL;39}40
41int main(void) {42    TrieNode* root = newNode();43    const char* words[] = {"car", "card", "care", "dog"};44    for (int i = 0; i < 4; i++) insert(root, words[i]);45    printf("search(card): %s\n", search(root, "card") ? "true" : "false");46    printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47    printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48    printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49    return 0;50}
이 코드를 C 플레이그라운드에서 실행하기

트라이 자주 묻는 질문

트라이는 무엇에 사용되나요?

트라이는 접두사 기반 기능을 구동합니다: 자동완성과 검색 제안, 맞춤법 검사기, IP 라우팅 테이블, 사전 조회 등입니다. "저장된 단어 중 이 접두사로 시작하는 것이 있는가?"에 빠르게 답해야 하는 곳이라면 어디서든 트라이가 빛을 발합니다.

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

삽입, 검색, 접두사 질의는 모두 O(m)으로 실행되며, 여기서 m은 단어 또는 접두사의 길이이고 저장된 단어 수와는 무관합니다. 트레이드오프는 메모리입니다: 공유 접두사는 한 번만 저장되지만 트라이는 많은 공간을 사용할 수 있습니다.

트라이와 해시 테이블의 차이는 무엇인가요?

해시 테이블은 완전한 키를 평균 O(1)에 조회하지만 접두사 질의에는 답할 수 없습니다. 트라이는 조회당 약간 더 느리지만 접두사 검색, 정렬된 순회, 자동완성을 자연스럽게 지원합니다 - 그것이 이러한 용도에서 선호되는 이유입니다.

이진 탐색 트리 대신 언제 트라이를 사용해야 하나요?

키가 문자열이고 접두사 검색이 필요할 때 트라이를 사용하세요: 키 길이에 대해 연산당 O(m)으로 동작하는 반면, 균형 이진 탐색 트리는 각 비교가 문자열을 훑고 그런 비교가 log n번 있으므로 O(m log n)이 듭니다. 키가 문자열 형태가 아니거나 메모리 오버헤드가 접두사 속도보다 더 중요할 때는 이진 탐색 트리가 더 나은 선택입니다.

트라이에서 단어의 끝은 어떻게 처리하나요?

각 노드는 단어 끝 플래그를 가지며, 삽입된 완전한 단어가 그곳에서 끝날 때에만 설정됩니다. 이것이 없으면 저장된 단어와 단순한 접두사를 구별할 수 없습니다 - 예를 들어 card를 삽입한 뒤 car의 노드는 존재하지만, car도 삽입된 경우에만 단어로 보고되어야 합니다.

트라이는 접두사를 공유함으로써 항상 메모리를 절약하나요?

항상은 아닙니다. 공유는 많은 키가 겹칠 때에만 도움이 됩니다; 길고 서로 다른 키에서는 각 문자가 자식 포인터를 가진 자기 자신의 노드가 되므로 트라이가 해시 집합보다 훨씬 더 많은 메모리를 쓸 수 있습니다. 공간이 문제라면 압축된 기수 트리(radix tree)가 자식이 하나뿐인 체인을 병합해 그 오버헤드를 줄입니다.