Trie(트라이) 정리

(참고)

www.geeksforgeeks.org/trie-insert-and-search/

Trie | (Insert and Search) - GeeksforGeeks

 

Trie는 reTrieval data structure을 의미하며, 검색 복잡도가 최적의 값이 되게 해줍니다. 만약 우리가 key를 이진 탐색 트리에 넣는다면, 아무리 균형잡힌 BST라도 M이 최대 문자열 길이고 N이 key의 개수라고 할 때, M*log N의 시간 복잡도를 가집니다. Trie를 사용하면 우리는 key를 O(M) 안에 찾을 수 있습니다. 다만 Trie는 추가적인 저장 공간을 필요로 합니다.

 

Trie의 장점은 다음과 같습니다.

1. M이 단일 문자열 길이라고 할 때, O(M)의 시간 복잡도를 가집니다. Hashing보다 빠르고, Collision이 없습니다.

2. 모든 단어를 알파벳 순으로 쉽게 조회할 수 있습니다.

3. prefix search(or 자동완성)를 간편하게 할 수 있게 합니다.

 

Trie의 가장 큰 단점은 저장 공간을 너무 많이 필요로 하는 것입니다. 각 노드에 대해서 너무 많은 포인터를 가지고 있어야 하기 때문입니다. 그래서 Ternary Search Tree가 딕셔너리로 구현하는 것보다 나을 수도 있습니다. Ternary Search Tree는 시간 복잡도가 tree의 높이 h에 대해 O(h)입니다. 따라서 Trie는 빠르지만 엄청난 저장공간을 필요로 하는 자료구조라고 정리할 수 있습니다.

 

출처: GeeksforGeeks

Trie의 모든 노드는 여러 개의 가지로 이루어져 있습니다. 각 가지는 key에 해당하는 문자를 나타냅니다. 주의할 점은 key가 끝나는 마지막 노드에는 마지막이라고 표시를 꼭 해주어야한다는 것입니다. 이 표시는 다른 노드와 확실히 구분할 수 있어야 합니다.

 

다음은 영어 알파벳 노드들을 나타내는 간단한 Trie 구조입니다.

Class TrieNode:
	def __init__(self):
		self.children = [None]*26
		self.isEndOfword = False

<삽입>

Trie에 key를 삽입하는 것은 간단합니다. key의 모든 문자가 독립적인 Trie 노드로 삽입됩니다. 

children은 포인터 배열로, 다음 단계의 trie 노드를 가리킵니다. 위 코드에서는 존재하지 않는 노드를 표기하기 위해 포인터 대신 Null값을 넣었습니다. 삽입할 key의 노드가 이미 존재하는지 확인할 때 사용합니다. 

마지막 노드는 isEndOfword 값을 True로 정해줍니다. 이렇기 때문에 key의 길이는 Trie의 깊이를 정하게 됩니다.

 

<조회>

key를 조회하는 것은 삽입과 비슷하지만, 문자열을 비교하고 다음 단계로 내려가는 작업만 합니다. 

이 작업은 문자열의 끝에 도달하거나 trie의 key가 부족할 경우 종료됩니다. 

 

<삭제>

삭제는 재귀 방식을 사용합니다. 키가 다른 키를 포함하거나 포함되어 있지 않을 경우, 모든 노드를 삭제합니다.

키가 다른 키에 포함되어 있다면, 단말 노드의 표시를 제거합니다. (isEndOfword를 False로 변경)

키가 다른 키를 포함하고 있다면, 포함된 키에 도달할 때까지 키의 끝에서부터 하나씩 제거합니다. 종료 시점의 위치는 포함된 키 중 가장 긴 키의 단말 노드입니다.