Trie 자료 구조

---

• Trie : 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 위의 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장된 것이다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.
• DFS 형태로 검색을 하면, to, tea, ted, ten, inn, in, inn 이라는 단어들이 자료구조에 들어가 있음을 알 수 있다.

트라이(Trie)의 예시

• 주황색으로 된 노드들이 입력된 문자열이다.
• 현재 be, bee, can, cat, cd가 들어가 있다.

사용 목적

목적

• 문자열의 탐색을 하고자 할 때, 시간복잡도를 줄여준다.
• 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다라는 단점도 있다.

시간 복잡도

• 제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때 시간 복잡도는
• 생성 시 시간 복잡도 : O(ML), 모든 문자열들을 넣으려니 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(ML)만큼 걸린다. 물론 삽입 자체만은 O(L)만큼 걸린다.
• 탐색 시 시간 복잡도 : O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸린다.

트라이(Trie)의 구현

Node

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

노드에는 세가지가 필요하다.

1. Key - 값으로 입력될 문자
2. Data - 문자열의 종료를 알리는 flag
3. Children - 자식 노드를 저장

Trie

class Trie:
	def __init__(self):
		self.head = Node(None)

	def insert(self, string):
		current_node = self.head

		for char in string:
			if char not in current_node.children: # 해당 알파벳이 자식 노드에 존재하지 않을 시
				current_node.children[char] = Node(char) # 새 노드 생성 후 자식 노드로 지정
			current_node = current_node.children[char]
		current_node.data = string # 문자열을 이루는 마지막 노드의 data에 string을 추가

	def search(self, string):
		current_node = self.head

		for char in string:
			if char in current_node.children: # 자식 노드가 char를 가지고 있을 경우 탐색 진행
				curreent_node = current_node.children[char]
			else:
				return False
		if current_node.data: # 마지막 노드가 data를 가지면 문자열인 관계로 True 반환
			return True
		else:
			return False

	def starts_with(self, prefix):
		current_node = self.head
		words = []
	
		for p in prefix:
			if p in current_node.children:
				current_node = current_node.children[p]
			else:
				return None

		current_node = [current_node]
		next_node = []
		
		while True:
			for node in current_node:
				if node.data:
					words.append(node.data)
				next_node.extend(list(node.children.values()))
			if len(next_node) != 0 :
				current_node = next_node
				next_node = []
			else:
				break
		return words

1. head를 빈 노드로 설정
2. Insert 함수 : 트리를 생성하기 위한 함수. 입력된 문자열의 문자를 하나씩 children에 확인 후 저장하고 문자열을 다 돌면 마지막 노드의 data에 문자열을 저장한다.
3. Search 함수 : 문자열이 존재하는지에 대한 여부를 리턴하는 함수이다.
4. starts_with 함수 : prefix단어로 시작하는 단어를 찾고 배열로 리턴하는 함수이다.