트라이란?
•
문자열을 효율적으로 저장하고 검색하기 위한 트리 구조 : 문자열 집합 탐색, 자동완성, 사전 검색 등에 사용
•
접두사 트리(Pretix Tree)라고도 함
사용 목적
•
문자열을 탐색할 때, 단순하게 하나씩 비교하면서 탐색하는 것보다 시간 복잡도 측면에서 훨씬 효율적
◦
빠르게 탐색 가능하다는 장점은 존재
◦
각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점 존재
프로세스(예시)
EX : “ab”, “abc”, “car”을 저장하기
•
“abc”
◦
첫번째 문자 “a” : 트라이 자료구조 내에는 아무것도 추가되어있지 않으므로, 헤드의 자식 노드에 “a” 추가
◦
“a” 노드에도 자식이 없으므로, “b”를 “a”의 자식 노드로 추가
◦
“c” 노드도 “b”의 자식 노드로 추가
◦
“abc”라는 단어가 끝 → 현재 노드에 abc라고 표시
•
“ab”
◦
현재 헤드의 자식 노드로 “a”가 이미 존재 → 기존에 있던 “a” 노드로 이동
◦
“b”도 “a”의 자식 노드로 이미 존재 → “b” 노드로 이동
◦
“ab”라는 단어가 끝 → 현재 노드에 ab를 표시
•
“car”
◦
현재 헤드의 자식 노드로 “a”만 존재하고 “c”는 존재 X → “c”를 헤드의 자식 노드로 추가
◦
“c”의 자식 노드가 없으므로 “a”를 “c”의 자식 노드로 추가
◦
“r” 또한 “c”의 자식 노드로 추가
◦
여기서 “car” 단어가 끝 → 현재 노드에 car 표시
트라이(Trie) vs 일반 트리(Tree) 비교
모두 계층 구조를 가지지만, 목적 & 작동 방식에서 차이가 존재
노드 비교
Trie
•
문자열의 개별 문자를 노드에 저장
•
각 문자를 순서대로 노드에 저장하고, 같은 접두사를 가진 단어는 해당 부분을 공유 → Prefix Tree
Tree
•
다양한 형태의 데이터를 노드에 저장 가능
•
노드의 데이터 형식이나 자식 노드 수는 자료구조의 목적에 따라 달라짐
구조와 데이터 저장 방식
Trie
•
각 문자를 순서대로 노드에 저장
•
자식 노드는 다음에 올 수 있는 문자를 표현
app, apple, apply 문자열의 경우
(공통된 접두사를 공유 → 데이터 중복 최소화)
Tree
•
자식 노드는 특정 데이터를 표현
•
자식 노드의 수나 트리의 깊이는 자료 구조에 따라 달라짐
이진트리의 경우
시간 복잡도
제일 긴 문자열 길이를 L, 총 문자열들의 수를 M이라고 할 때,
•
생성 시간 복잡도
◦
O(M * L)
◦
모든 문자열들을 넣어야하니 M개에 대해 트라이 자료구조에 넣는건 L만큼 걸려서 O(M * L)
•
탐색 시간 복잡도
◦
O(L)
◦
트리를 타고 들어가봤자 최대 L만큼만 탐색하므로 O(L)
코드로 확인해볼까요?
버전1
class TrieNode:
def __init(self):
self.children = dict()
self.is_end_of_word = False
class Trie:
def __init(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
# 문자가 없으면 새로 추가
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
# 단어 순회가 끝나면, 끝나는 지점 표시
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False # 중간글자가 없으면 실패
node = node.children[char]
return node.is_end_of_word # 끝 지점이 완전한 단어인지 확인
def starts_with(self, prefix):
node = self.root
# 접두사만큼이 있는지 확인
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
# 끝지점에 잘 도착한 경우라면 -> 접두사가 존재한다는 뜻
return True
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("bat")
print(trie.search("apple")) # True
print(trie.search("app")) # True
print(trie.search("ap")) # False
print(trie.starts_with("ap")) # True
print(trie.starts_with("ba")) # True
Python
복사
버전2
class Node:
def __init__(self, key, data=None):
self.key = key
self.data = data
self.children = {}
class Trie:
def __init__(self):
self.head = Node()
def insert(self, string):
current_node = self.head
for char in string:
if char not in current_node.children:
current_node.children[char] = Node()
current_node = current_node.children[char]
# 문자가 모두 삽입된 시점의 마지막 노드에 전체 문자열 데이터 저장
current_node.data = string
def search(self, string):
current_node = self.head
for char in string:
if char in current_node.children:
current_node = current_node.children[char]
else:
return False
if current_node.data != None:
return True
Python
복사
참고자료
