Trie 란?

트라이의 정의예요.

• "문자열을 저장하고 효율적으로 탐색하기 위한 트리 기반 자료구조"

다른이름으로는 Prefix Tree 라고도 불리구요. 공통 접두사를 공유하는 방식으로 문자열을 저장해요.

이게 다인데요... 진짜 이게 다예요.

예를 들어서, 이런 단어들이 있다고 해볼게요.

["cat", "can", "cap", "dog"]

얘네를 이렇게 저장하는 거예요.

벌써 그냥 아주 야무지죠?

자료구조중 해시테이블과 흡사해요. 해시테이블은 해시함수를 기반으로 인덱싱 검색을 하잖아요?
이건 해시함수가 아니라 그냥 문자열 그 자체를 기준으로 인덱싱을 해요.

물론 똑같은 문자가 여러개 있을리는 없으니 그 자체로 유니크하죠!

그래서 트라이의 특징은?

Trie 의 특징

• 문자열을 문자 단위로 나눠서 계층적으로 저장해요!
• 각 트리의 노드 하나는 "문자 하나" 만 나타냄!
• 공통된 접두사(c)를 갖는 문자열은 같은 경로 공유!
• 탐색, 삽입, 삭제 모두 문자 길이에 비례한 시간복잡도 O(L) (L은 문자열 길이)

트라이를 사용하면 문자열 탐색,삽입,삭제 등이 굉장히 빠르기 때문에 아주 엄청난 장점이예요.

근데 단점도 있어요.

문자열 하나하나를 노드를 생성해서 전부 저장하다 보니..

메모리 사용량이 엄청 큽니다. 홀리쩻

구현도 단순 배열이나, 해시맵 기반 자료구조에 비하면 좀 복잡하다잉

Trie와 자동완성(Autocomplete)

Autocomplete란?

입력한 접두사(prefix)를 기반으로 가능한 모든 문자열(단어)들을 자동으로 제안하는 기능이예요.
검색창, IDE 자동완성, 검색어 추천 등에 사용되는데요.
Trie 랑 싹맞죠?

참고용 전체코드

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        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 autocomplete(self, prefix):
        node = self._find_node(prefix)
        if not node:
            return []

        results = []

        def dfs(current_node, path):
            if current_node.is_end:
                results.append(path)
            for c, next_node in current_node.children.items():
                dfs(next_node, path + c)

        dfs(node, prefix)
        return results

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

우리모두 트라이쓰기 츄라이~~