[자료구조] 트라이(Trie)

트라이(Trie)는 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 검색 트리 자료구조로, 전형적인 다진 트리의 형태를 띤다.

트라이라는 이름은, 검색을 뜻하는 영단어 'retrieval'의 중간 음절에서 따온 것이다.

트라이에서 문자열의 길이만큼 탐색하면 원하는 결과를 찾을 수 있다.

가령 apple이라는 단어의 경우, a > p > p > l > e, 총 5번의 탐색으로 apple에 관한 정보를 찾을 수 있게 된다.

트라이는 문자열(string)을 위한 트리이므로 사실상 문자(character) 개수만큼이나 많은 자식 노드들을 갖는 트리이다.

---

트라이의 활용

• 단어 자동 완성기
• 사전 검색
• 자연어 처리 분야에의 문자열 탐색 (형태소 분석기에서 분석 패턴을 트라이로 만들어두고 자연어 문장에 대해 패턴을 찾아 처리하는 등에 활용)

---

구현

TrieNode의 멤버 변수 word는, 해당 문자로 끝나는 문자열이 트라이에 존재하는지를 나타낸다.
가령 단어 apple에서, e에 해당하는 TrieNode의 word 값이 True로 저장되어 apple이 트라이에 존재함을 나타낸다.

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.word = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    def _traversal(self, string: str) -> Optional[TrieNode]:
        node = self.root
        for char in string:
            if char not in node.children:
                return
            node = node.children[char]
        return node

    def search(self, word: str) -> bool:
        node = self._traversal(word)
        return node.word if node else False

    def start_with(self, prefix: str) -> bool:
        return True if self._traversal(prefix) else False