정의와 성질
문자열을 효율적으로 처리하기 위한 트리 자료구조
시간 - 단어S를 삽입/탐색/삭제할 때 O(len(S))
공간 - 문자열을 그냥 배열에 저장하는 것 보다 최대 4X글자의 종류 배 만큼 더 사용한다.(메모리 사용량에서 병목이 될 수 있음)
이론적으로 생각할 때 이진검색트리는 최악의 경우 삽입, 탐색, 삭제가 모두 O(len(S) X lgN)이 걸린다.
해시로 구현한다면 삽입,탐색, 삭제가 모두 O(1)인 것 같지만 해시값을 계산할때 O(len(S))가 필요하기도 하고 또 문자열 간의 비교도 발생하기 때문에 O(len(S))라고 볼 수 있으나 실제로는 충돌에 따라 O(len(S))보다 성능이 떨어질 수 있다.
반면에 트라이는 O(len(S))에 정직하게 동작한다. 그러나 트라이는 메모리를 아주 많이 사용한다는 단점이 있다. 이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진검색트리에 비해 훨씬 느리다. 일반적인 상황에서는 해시나 이진검색트리를 사용하는게 좋으나 트라이의 성질을 사용해야하는 문제가 여럿 존재한다.
기능과 구현
트라이는 삽입 탐색 삭제 이 모든 연산을 할 때 정점을 옮겨다닌다.
Insert
apple을 삽입한다고 가정하면 현재 보고 있는 루트에는 값이 A인 정점이 없다.(아무것도 없는 루트라고 가정했을 때)
루트의 자식노드에 a를 추가해준다. 그 다음은 순서대로 자식노드로 넣어준다.
apple이 추가된 상태에서 apply를 삽입한다면 루트 자식노드에 A가 있고 그 아래로 죽 appl까지 내려 간 다음 l의 자식노드에 y가 없기 때문에 y를 삽입해준다.
삽입에서 주의할 점은 단어의 마지막을 트라이에 삽입했다면 마지막 노드라는 표시를 해줘야 한다.
Fetch
fetch도 마찬가지로 루트정점부터 시작해 일치하는 값이 있는지 자식노드를 타고 내려가면 된다.
여기서 주의할 점은 삽입에서 표시한 마지막 노드다.
예를들어 BANANA라는 단어를 삽입하고 BAN을 찾으려고 한다면 BAN은 트리 안에 있기 때문에 있는 단어라고 받아들일 수도 있다. 트라이 안에 있다고 해도 마지막 글자가 트리 내부에서 마지막이라는 표시가 없다면 그건 트리 내부에 없는 것이다.
Erase
BANANA를 삽입하고 BAN을 삽입했다고 가정하면 이 트리에서 BAN을 지우고 싶다면 BAN을 따라 간 다음 N에 표시한 마지막 글자라는 표시를 지워주면 된다.
이렇게 하는 이유는 BAN을 그냥 지웠을때 트라이의 구조를 헤칠 수 있기 때문이다.
그렇기 때문에 트라이는 삭제를 하더라도 이전에 삽입한 정점들은 계속 메모리에 남아있게 되어서 메모리의 측면에서 비효율적이게 되고 삭제가 자주 발생하는 환경에서는 트라이가 적합하지 않다.
ROOT = 1 # 루트는 1로 고정
unused = 2 # 새로 정점이 추가될 때 마다 증가시킨다.
MX = 10000 * 500 + 5 # 길이가 최대 500인 문자열이 10000개 들어오는 문제라면 이렇게 둘 수 있다.
# 루트가 1부터 시작하기 때문에 여유값 5를 둔다.
check = [False] * MX
nxt = [[-1] * 26 for _ in range(MX)] # 문자열의 종류에 따라 칼럼값을 변경(현재는 알파벳 수)
def char_to_int(char):
return ord(char) - ord('A')
def insert(string):
global unused
cur = ROOT
for char in string:
cur_char_int = char_to_int(char)
if nxt[cur][cur_char_int] == -1:
nxt[cur][cur_char_int] = unused
unused+=1
cur = nxt[cur][cur_char_int]
check[cur] = True
def find(string):
cur = ROOT
for char in string:
cur_char_int = char_to_int(char)
if nxt[cur][cur_char_int] == -1:
return None
cur = nxt[cur][cur_char_int]
if check[cur]:
return string
def erase(string):
cur = ROOT
for char in string:
cur_char_int = char_to_int(char)
if nxt[cur][cur_char_int] == -1:
return
cur = nxt[cur][cur_char_int]
check[cur] = False
insert("BANANA")
print(find("BANANA"))
erase("BANANA")
print(find("BANANA"))메모리 절약 방법
| 자식 저장 방법 | 시간복잡도 | O(26 * MX) |
|---|---|---|
| 고정된 크기의 배열 | O(len(S)) | O(MX) |
| 동적배열 | O(26 * len(S)) | O(MX) |
| 연결리스트 | O(26 * len(S)) | O(MX) |
| 이진검색트리 | O(lg26 * len(S)) | O(MX) |
| 해시 | O(len(S)) | O(MX) |
연습문제
boj-14425
import sys
input = sys.stdin.readline
def char_to_int(char):
return ord(char) - ord("a")
def insert(string):
global unused
cur = ROOT
for char in string:
cur_char_int = char_to_int(char)
if nxt[cur][cur_char_int] == -1:
nxt[cur][cur_char_int] = unused
unused +=1
cur = nxt[cur][cur_char_int]
check[cur] = True
def is_in_origin_words(string):
cur = ROOT
for char in string:
cur_char_int = char_to_int(char)
if nxt[cur][cur_char_int] == -1:
return False
cur = nxt[cur][cur_char_int]
return check[cur]
if __name__ == "__main__":
N, M = map(int, input().split())
ROOT = 1
MX = 10000 * 500 + 5
check = [False] * MX
nxt = [[-1] * 26 for _ in range(MX)]
unused = 2
answer = 0
for _ in range(N):
insert(input())
for _ in range(M):
answer += int(is_in_origin_words(input()))
print(answer)