트라이(Trie)

트라이

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

트라이의 특징

• 검색어 자동완성, 사전찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탬삭, 삽입은 O(L)만큼 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

Trie 생성하기

트라이 구조

• 루트는 비어있다.
• 각 간선(링크)은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

파이썬에서 사용방법

(트리구조로 사용)

class Node:
    def __init__(self, value = "") :
        self.value = value
        self.children = dict()

class Trie:
    def __init(self):
        self.root = Node()
    
    def insert(self, string):
        curr_node = self.root
        
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(curr_node.value + char)
            curr_node = curr_node.children[char]
            
     def has(self, string):
         curr_node = self.root
         
         for char in string:
             if char not in curr_node.children:
                 return False
             curr_node = curr_node.children[char]
         return True