트라이 (Trie)
- 각 노드에 문자를 저장하는 트리 기반의 자료구로, 트리를 아래쪽으로 순회하면 단어 하나가 나온다.
- 트라이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다.
- 먄악 트리에서 연관된 접두사를 반복적으로 검색해야 하는 경우, 트리의 현재 노드를 참조값으로 넘긴다면 매번 검색할 때마다 루트에서 시작할 필요없이 자식 여부만 확인하면 된다.
구현
# Node 클래스
# key: 해당 노드의 문자, child: 자식 노드
# data: 문자열이 끝나는 위치를 알려주는 역할 (해당 노드에서 끝나는 문자열이 없으면 None)
class Node:
def __init__(self, key, data=None):
self.key = key
self.data = data
self.child = dict()
# Trie 클래스
class Trie:
def __init__(self):
self.root = Node(None)
# 문자열 삽입
def insert(self, word):
curr_node = self.root
# 삽입할 word의 각각의 문자에 대해 자식 Node를 만든다.
for char in word:
# 자식 Node들 중 같은 문자가 없으면 새로운 Node 생성
if char not in curr_node.child:
curr_node.child[char] = Node(char)
# 같은 문자가 있으면 노드를 따로 생성하지 않고 해당 노드로 이동
curr_node = curr_node.child[char]
# 문자열이 끝난 지점의 노드의 data 값에 해당 문자열 입력
curr_node.data = word
# 문자열 조회
def search(self, word):
# 가장 위에 있는 노드에서부터 탐색 시작
curr_node = self.root
for char in word:
if char not in curr_node.child:
return False
curr_node = curr_node.child[char]
# 탐색이 끝난 후 해당 노드의 data 값이 존재한다면 탐색 성공
if curr_node.data != None:
return True
return False
'Python > Algorithm' 카테고리의 다른 글
그래프 관련 알고리즘 (0) | 2022.03.01 |
---|---|
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
힙과 우선순위 큐 (0) | 2022.02.27 |
트리의 종류와 트리 순회 (0) | 2022.02.26 |
최단 경로 알고리즘 (0) | 2022.02.25 |