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
Author And Source
이 문제에 관하여(TIL 017 트라이 Trie), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chosh/트라이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)