- 트라이(Trie): 문자열을 저장하고 효율적으로 탐색하기 위한 “트리” 형태의 자료구조
- 자동 완성기능, 사전 검색 등 문자열을 탐색하는 데 특화되어 있는 자료구조
- 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or 탐색 트리(retrieval tree) 라고도 한다.
트라이 장단점
- 트라이는 문자열 검색을 빠르게 한다.
- 문자열을 탐색할 때, 하나 하나 씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.
- 각 노드에서 자식들에 대한 포인터 들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점이 있다.(메모리 측면에서 비효율적)
1. 트라이에 문자열 저장
- ‘abc’ 트라이에 삽입
- 첫번 째 문자는 ‘a’이다. 초기에 트라이 구조 내에는 아무것도 없으므로 Head의 자식 노드에 ‘a’를 추가해준다.
- ‘a’ 노드에도 현재 자식이 하나도 없으므로, ‘a’의 자식 노드에 ‘b’를 추가해준다.
- ‘c’도 마찬가지로 ‘b’의 자식 노드로 추가해준다.
- ‘abc’ 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc 라고 표시한다. (Data)
- ‘ab’ 트라이에 삽입
- 현재 Head의 자식 노드로 이미 ‘a’가 존재한다. 따라서 ‘a’노드를 추가하지 않고 기존에 있는 ‘a’노드로 이동한다.
- ‘b’도 ‘a’의 자식 노드로 이미 존재하므로 ‘b’의 노드로 이동한다.
- ‘ab’의 단어가 여기서 끝이므로 현재 노드에 ab를 표시한다.
- ‘car’ 트라이에 삽입
- Head의 자식 노드로 ‘a’만 존재하고 ‘c’는 존재하지 않는다. 따라서 ‘c’를 자식노드로 추가한다.
- ‘c’에 대한 자식 노드가 없으므로 마찬가지로 ‘a’를 추가한다.
- ‘a’의 자식 노드가 없으므로 마찬가지로 ‘r’을 추가한다.
- ‘car’단어가 여기서 끝이므로 현재 노드에 ‘car’를 표시한다.
2. 트라이에서 문자열 탐색
- 위의 트라이에 ‘abc’문자열이 있는지 탐색해보자.
- Head의 child에 ‘a’가 존재 → ‘a’노드 (key=’a’)로 이동
- ‘a’노드의 child에 ‘b’가 존재 —> ‘b’노드(key=’b’)로 이동
- ‘b’노드의 child에 ‘c’가 존재 —> ‘c’노드로 이동 (key=’c’)
- 문자열 탐색이 완료됨 —> 현재 노드에 데이터 값이 존재 —> 문자열 존재
- ‘ca’ 라는 문자열이 있는지 탐색해보자
- Head의 child에 ‘c’가 존재 —> ‘c’노드(key=’c’)로 이동
- ‘c’노드의 child에 ‘a’가 존재 —> ‘a’노드(key=’a’)로 이동
- 문자열 탐색이 완료됨 —> 현재 노드에 데이터 값이 없음 —> 문자열 존재 안함
구현
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
for char in string:
if char not in curr_node.children:
curr_node.children[char] = Node(char)
curr_node = curr_node.children[char]
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
if curr_node.data is not None:
return Trueref. https://www.geeksforgeeks.org/trie-insert-and-search/
배우고 적용하고 개선하기