트라이

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

트리구조로 간선은 이전 정점으로 새롭게 추가되는 문자 정보를 가지고 있다.

정점은 이전 정점으로부터 더해진 문자열 정보를 가지고 있다.

이런식으로 미리 정의한 문자열로 자동완성을 구현할 수 있다.

• 문자열을 탐색할 때 효율적
• L이 문자열이의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

구현

1. 루트 노드는 비어있다.
2. cat라는 문자열을 추가할 때
   1. c를 키로 가지는 자식을 루트 노드에 추가한다.
   2. a를 키로 가지는 자식을 c를 키로 가지는 노드에 추가한다.
   3. t를 키로 가지는 자식을 a를 키로 가지는 노드에 추가한다.

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

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