트라이

트라이란?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조.

 

최대 20개의 알파벳을 갖는 10000개의 문자열이 있다고 가정할때 일반 배열에 문자열을 저장할 시, 특정 문자열의 존재여부 판단은 10000번의 연산이 필요하다. 하지만 Trie에 저장할 시 20번 안팎의 연산으로 문자열의 존재여부 판단이 가능하다. 트라이의 예시는 아래의 그림과 같다.

 

 

 

 

["A", "to", "tea", "ted", "ten", "i", "in", "inn"] 을 키로 둔 트라이의 예시이다. 동일한 키를 배열에 담고 "tea"의 존재 여부를 판단하려 했다면 최악의 경우 8번의 연산이 필요하지만 트라이에서는 문자열의 길이만큼의 연산으로 존재 여부가 판단이 가능하다.

 

 

트라이 예시 문제

https://leetcode.com/problems/implement-trie-prefix-tree/

Implement Trie (Prefix Tree) - LeetCode

 

트라이를 구현해보는 문제가 리트코드에 있으니 풀어보면서 익히면 좋다.

 

정답 코드는 아래와 같다.

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

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 search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True