트라이(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.