트라이(Trie)

in Blog / 알고리즘

라이(Trie)는 문자열을 효율적으로 저장하고 탐색하기 위한 트리 기반 자료구조야. 특히 단어 집합이나 사전(dictionary) 같은 걸 다룰 때 매우 유용하지.

트라이(Trie)란?

  • 트라이(Trie)는 “retrieval”에서 유래된 말이야. 흔히 prefix tree(접두사 트리) 라고도 불려

  • 주로 문자열을 문자 단위로 노드에 나누어 저장해서, 문자열 검색을 빠르게 수행할 수 있어

  • 각 노드는 하나의 문자(character)를 나타내고, 루트에서 리프까지의 경로가 하나의 문자열이 돼

예를 들어 [“cat”, “can”, “dog”] 이라는 단어들이 있을 때, 트라이 구조는 다음과 같이 생겨:

(root)
 ├── c
 │   ├── a
 │   │   ├── t (*)
 │   │   └── n (*)
 └── d
     └── o
         └── g (*)

여기서 (*)는 단어의 끝을 나타내는 마커야 (종종 is_end 플래그를 씀)

트라이의 특징

특징설명
검색 시간O(L), 여기서 L은 문자열 길이
공통 접두사 저장중복을 줄여 메모리 절약 가능
자동완성 기능 구현에 적합접두사 기반 검색이 빠름
삽입/검색/삭제모두 O(L) 시간 복잡도 (L은 문자열 길이)

트라이의 주요 연산

  • 삽입(Insert) : 문자열의 각 문자를 따라가며 노드가 없으면 새로 생성

  • 검색(Search) : 문자열의 각 문자를 따라가며 없으면 False, 끝까지 가면 True

  • 접두사 검색(StartsWith) : 문자열이 트라이 내 단어의 접두사인지 확인

트라이 파이썬 구현

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 char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

    def _find_node(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

마무리

트라이가 어디에 사용되는지 알려줄게게

  • 자동완성 기능 (e.g. 검색창)

  • 사전(word dictionary) 구현

  • 접두사 중복 방지

  • 전화번호부 정리

  • 문자열 탐색 최적화 문제 (e.g. LeetCode, 백준 등)

© 2022 JeongHwan Yun.