소개
트라이란 문자열의 집합을 트리로 관리하는 자료구조이다. 물론 문자열이 아니더라도 어떠한 수열의 정보를 저장하는 데에 쓰일 수 있다. 트라이를 사용하면 문자열 집합에 임의의 문자열이 속하는지를 빠르게 구할 수 있다.
원리
다음 문자열 집합을 트라이로 저장해보자.
문자열의 각 문자를 경로라고 생각하고 트리를 구성하면 된다. 이를테면
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
다음으로 문자열
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
저장을 마친 후 트라이의 모습은 다음과 같다. 초록색으로 표시된 정점는 집합 내의 어떠한 단어의 종점임을 나타낸다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
문자열 집합으로부터 트라이를 만들어낼 때의 시간복잡도는 문자열 집합의 모든 문자열의 길이의 합인
- 문자열이 존재하는 경우
주어진 문자열 =
문자열과 매칭되는 루트가 존재하므로 이 문자열은 집합에 존재한다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
- 문자열이 존재하지 않는 경우
주어진 문자열 =
문자열과 매칭되는 루트가 존재하지 않으므로 이 문자열은 집합에 존재하지 않는다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
주어진 문자열 =
문자열과 매칭되는 루트는 존재하지만, 초록색 정점에서 끝나지 않으므로 이 문자열은 집합에 존재하지 않는다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
트라이에 임의의 문자열이 존재하는지를 평가할 때의 시간복잡도는 그 문자열의 길이인
구현
class Trie:
# 트라이의 각 정점이다.
# 알파벳 간선과 end_flag를 저장한다.
class Node:
def __init__(self):
self.edge: dict[str: 'Trie.Node'] = { }
self.end_flag = False
def __init__(self):
self.root = Trie.Node()
# 트라이에 문자열을 추가한다.
def add(self, string: str):
now = self.root
for s in string:
if s not in now.edge:
now.edge[s] = Trie.Node()
now = now.edge[s]
now.end_flag = True
# 트라이에 문자열이 포함되어있는지를 검사한다.
def contains(self, string: str) -> bool:
now = self.root
for s in string:
if s not in now.edge:
return False
now = now.edge[s]
return now.end_flag