트라이(Trie)
는 문자열을 저장하고 효율적으로 탐색하기 위한 트리
형태의 자료구조이다.
우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.
래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree)라고도 한다. 트라이
는 retrieval tree에서 나온 단어이다.
예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)
이다.
트라이(Trie)
는 문자열 검색을 빠르게 한다.
문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.
각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. (메모리 측면에서 비효율적일 수 있음!)
'abc', 'ab', 'car' 단어들을 'abc'부터 트라이
에 저장한다고 가정해보자.
'abc' 트라이(Trie)
에 삽입
트라이
자료구조 내에는 아무것도 없으므로 Head의 자식노드에 'a'를 추가해준다.'ab' 트라이(Trie)
에 삽입
'car' 트라이(Trie)
에 삽입
모든 그림의 출처 : 링크
Python의 Dictionary
자료형을 이용하여 트라이(Trie)
를 구현해보자.
먼저 Node를 아래와 같이 생성한다.
Node
- key에는 해당 노드의 문자가 들어가고, child에는 자식노드가 포함되게 된다.
- data는 문자열이 끝나는 위치를 알려주는 역할을 한다.
(Ex) 'car'가 'r'에서 끝날 때, 'r'을 key로 가지는 노드의 data에 'car'를 입력한다.- 해당 노드에서 끝나는 문자열이 없을 경우에는 그대로 None으로 내비둔다.
class Node(object):
def __init__(self, key, data=None):
self.key = key
self.data = data
self.children = {}
두 번째, Dictionary
자료형을 이용하여 트라이(Trie)
를 구현해보자.
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
# 삽입할 String 각각의 문자에 대해 자식Node를 만들며 내려간다.
for char in string:
# 자식Node들 중 같은 문자가 없으면 Node 새로 생성
if char not in curr_node.children:
curr_node.children[char] = Node(char)
# 같음 문자가 있으면 노드를 따로 생성하지 않고, 해당 노드로 이동
curr_node = curr_node.children[char]
# 문자열이 끝난 지점의 노드의 data값에 해당 문자열을 표시
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
# 탐색이 끝난 후에 해당 노드의 data값이 존재한다면
# 문자가 포함되어있다는 뜻이다!
if curr_node.data is not None:
return True
트라이
의 생성 시간 복잡도는 O(MxL)
, 탐색 시간 복잡도는 O(L)
이다.트라이
에 넣는건 가장 긴 문자열 길이인 L만큼 걸리므로 O(MxL)
의 시간 복잡도를 가진다. (삽입은 O(L)
이다.)O(L)
의 시간 복잡도를 가진다.위에서 트라이
자료구조에 데이터를 삽입해보았는데, 이를 바탕으로 트라이
에서 문자열 탐색을 진행해보려 한다.
위의 트라이
에 'abc' 문자열이 있는지 탐색해보자.
'ca'라는 문자열이 있는지 탐색해보자.
잘 설명되어 있어서 쉽게 이해했습니다 ㅎㅎ