트라이_Trie

트라이(Trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색등 문자열을 탐색하는데 특화 되어있는 자료구조
• 래딕스 트리(radix tree) or 접두사 트리
• (prefix tree) or 탐색 트리(retrieval tree) 라고도 한다. 트라이는 retrieval 에서 나온 단어다.

트라이 장단점

• 장점
  • 트라이는 문자열 검색을 빠르게 한다.
  • 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 더 효율적이다.
• 단점
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장공간의 크기가 크다는 단점도 있다.
• 트라이의 생성 시간복잡도는 O(MxL): 탐색 시간복잡도 O(L)
  • 가장 긴 문자열 길이 L
  • 총 문자열의 수 M

class Node(Object):
	def __init__(self,key,data = None):
		self.key = key
		self.data = data
		self.children = {}

class Trie(Object):
	def __init__(self):	
		self.head = node(None)
	# 문자열 삽입
	def insert(self,string):
		curr_node = self.head
		for char in string:
			if char not in curr_node.children:
				curr_node.children[char]
			curr_node = curr_node.children[char]
		curr_node.data = string

	def search(self, string):
		curr_node = self.head
		for char in string:
			if char in curr_node.children:
				curr_node = curr_node.children[char]
			else:
				return False
		if curr_node.data is not None:
			return True