TIL 017 트라이 Trie

📕 트라이

트라이는 여러 문자열을 효과적으로 담는 자료구조이다.
다음 이미지를 기억하면 한눈에 이해할 수 있다. 만약 이를 트라이 구조를 쓰지 않는다면 알파벳만큼의 배열이 필요하다.

[사진 출처]https://blog.naver.com/kks227/220938122295

트라이의 활용은 인터넷 검색창을 떠올리자, 자동완성을 트라이로 구현할 수 있다.

다음은 트라이의 기본 구조다.

노드
-key : 현재 노드 철자
-child : 다음 노드(주소)를 담는 dictionary
-data : 만약 단어의 끝이라면 단어 전체를 담는다. (이렇게 하면 단어를 알기 위해 거꾸로 올라갈 필요가 없다.)
(leaf 등 중간에 정보들을 표기해 놓아 응용할 수 있다.)

트라이
root를 먼저 선언해준다.
삽입은 child에 철자가 없다면 node를 추가하고, 다음 노드로 내려간다. 단어의 끝이라면 표기해둔다.

class node:
    def __init__(self,key,data=None):
        self.key = key
        self.data = data
        self.child = {}

class trie:
    def __init__(self):
        self.head = node(None)

    def insert(self,string):
        cur_node = self.root
        for char in string:
            if char not in cur_node.child:
                cur_node.child[char] = node(char)
            cur_node = cur_node.child[char]
        cur_node.data = True