비선형 자료구조 - 트라이

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

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

트라이는 실무에서, 특히 자연어 처리(NLP)분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다.

트라이 구현

트라이의 insert, search, startwith 메소드를 구현하라.

• 풀이: 딕셔너리를 이용해 간결한 트라이 구현

# 트라이의 노드
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:1
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]

        return True