Trie란
트라이는 실무에 매우 유용하게 쓰이는 트리 형태의 자료구조로서, 특히 자연어 처리(NLP)분야에서 문자열 탐색을 위한 자료구조로 널리 쓰입니다.트라이는 검색을 뜻하는 'retrieval'의 중간 음절에서 용어를 따왔습니다.
저는 알고리즘 문제를 풀 때 처음 트라이를 접했는데, 그 당시 문제에서는 트라이를 이용해서 구글이나 네이버등의 검색 포털에서 이용되는 문자 자동완성 기능을 구현해야 했습니다.
위에 보이는 트리의 루트로부터 자식들을 따라가면서 생성된 문자열들이 트라이에 저장되어 있다고 볼 수 있으며, 각각의 문자 단위로 색인을 구축한 것 과 유사합니다.
Trie의 사용 목적
사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.
시간 복잡도
문자열 집합의 개수와 상관 없이 찾고자 하는 문자열의 길이가 시간 복잡도가 됩니다. 즉, 문자열의 길이가 m이라면 시간 복잡도는 O(m)입니다.
트라이를 구현할 때, n(문자열의 수)과 m(문자열 최대 길이)이 상대적으로 작다면 배열을 사용할 텐데, 현재 노드의 위치를 i, j번째 문자라고 한다면 trie[i][j]의 위치를 조회하는 건 O(1)에 수행이 가능합니다. 여기서 문자열의 길이만큼, 즉 m번을 수행하니 O(m)의 시간이 소요됩니다.
만약 n과 m이 크다면, map을 이용해서 트라이를 구현하기도 하며, 이 때 시간 복잡도는 O(mlogn)이 됩니다.(map은 기본적으로 레드블랙 트리를 기반으로 하기 때문에 탐색 시에 O(logn)소요)
Trie 구현
파이썬으로 직접 트라이를 구현해보겠습니다.
import collections
class TrieNode:
def __init__(self):
self.word = False
self.children = collections.defaultdict(TrieNode)
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
node = node.children[char]
node.word = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.word
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
위의 구현은 리트코드의 208번 Implement Trie문제의 스켈레톤 코드와 '파이썬 알고리즘 테스트'책을 바탕으로 작성되었습니다.
트라이의 각 노드는 자식 노드 딕셔너리와, 해당 노드가 단어의 끝부분인지 여부를 판단할 수 있는 word라는 플래그가 있습니다.
처음 Trie 클래스를 생성하면 루트노드로 TrieNode가 생성됩니다. insert 함수를 통하여 단어 삽입 시 자식 노드가 점점 깊어지면서 문자 단위의 다진 트리 형태가 됩니다. 예를 들어 apple을 입력할 경우, 마지막 'e'에 해당하는 자식 노드의 word값은 True이고, 나머지 'a', 'p', 'p', 'l'의 word값은 False입니다.
search함수는 단어가 존재하는지 여부를 판별하는 함수이고, startsWith는 해당 문자열로 시작하는 단어가 존재하는지 여부를 판별해줍니다. 두 함수 모두 루트 노드부터 DFS로 탐색을 하고, search의 경우에는 마지막 단어의 word 프로퍼티의 boolean값을 리턴합니다. startsWith는 search와 거의 같지만, 마지막에 모든 단어를 찾았을 경우 True를 리턴합니다.
참조
파이썬 알고리즘 인터뷰
https://twpower.github.io/187-trie-concept-and-basic-problem
