[Algorithm Part 2] 7. Tries

이번 글에서는, Tries에 대해 살펴볼 것이다.

Tries는 문자열(=string) key에 특화된 symbol table이다.

문자열을 key로 둘 때, Tries는 기존 Balanced Search Tree 혹은 Hash Table보다

(문자열의 모든 문자 조사를 피함으로써,) 더 좋은 성능을 보인다.

---

1. R-way tries

Representation

다음 조건을 만족하는 트리로 표현할 수 있다.

모든 노드는 value와 R개의 자식 노드를 가지고 있다.

 

key(=문자열)는 root노드에서 해당 노드까지의 경로로 알 수 있다.

예를 들어, 경로가 115(ascii s) → 97(ascii e) → 101(ascii a)인 경우, 노드의 key는 "sea"다.

따라서, 따로 노드에 key를 저장할 필요가 없다.

Operations

1. search

key(=문자열)의 맨 왼쪽 문자부터 차례대로, 각 문자에 해당되는 노드를 탐색해 나간다.

1. search hit: 마지막 노드의 value가 non-null인 경우
2. search miss: 탐색 도중 null 노드를 만난 경우, 혹은 마지막 노드의 value가 null인 경우

2. insert 

key(=문자열)의 맨 왼쪽 문자부터 차례대로, 각 문자에 해당되는 노드를 탐색해 나간다.

1. null 노드를 탐색한 경우, 새로운 노드를 만든다.
2. 마지막 노드를 만난 경우, value를 초기화 한다.

3. delete

key(=문자열)의 맨 왼쪽 문자부터 차례대로, 각 문자에 해당되는 노드를 탐색해 나간다.

1. 마지막 노드의 value를 null로 초기화 한다.
2. 만약 현재 노드의 value와 모든 자식 노드가 null인 경우,
   현재 노드를 null로 초기화하고 부모 노드로 이동한다.
3. 2번을 반복한다.

R이 클 때는 메모리 사용량이 매우 높기 때문에, R이 작을 때 적절한 방법이다.

---

2. Ternary Search Tries

TST는 R-way tries의 단점인 "R이 클 때 메모리 사용량이 매우 높음"을 극복한 자료구조이다.

Representation

다음 조건을 만족하는 트리로 표현할 수 있다.

각 노드는 1). 문자(char), 2). value 그리고 3). 자식 노드 3개를 가지고 있다.

1. 왼쪽 서브 트리의 모든 노드는 char보다 낮은 key를 가진다.
2. 중간 서브 트리의 모든 노드는 char와 동일한 key를 가진다.
3. 오른쪽 서브 트리의 모든 노드는 char보다 높은 key를 가진다.

Operations

1. search

key(=문자열)의 맨 왼쪽 문자부터 차례대로, 각 문자에 해당되는 노드를 탐색해 나간다.
(중간 자식 노드로 이동할 때만 key를 다음 문자로 변경한 후, 탐색을 이어간다.)

1. search hit: 마지막 노드의 value가 non-null인 경우
2. search miss: 탐색 도중 null 노드를 만난 경우, 혹은 마지막 노드의 value가 null인 경우

2. insert

key(=문자열)의 맨 왼쪽 문자부터 차례대로, 각 문자에 해당되는 노드를 탐색해 나간다.

(중간 자식 노드로 이동할 때만 key를 다음 문자로 변경한 후, 탐색을 이어간다.)

1. null 노드를 탐색한 경우, 새로운 노드를 만든다.
2. 마지막 노드를 만난 경우, value를 초기화 한다.

Performance

implementation	search hit	search miss	insert	space
red-black BST	$L + c\lg^2 N$	$L + c\lg^2 N$	$L + c\lg^2 N$	4N
hashing	L	L	L	4N to 16N
R-way trie	L	$\log_R N$	L	(R + 1)N
TST	$L + \ln N$	$\ln N$	$L + \ln N$	4N

 

R-way trie와 다르게 TST는 메모리 사용량이 상대적으로 적어, 어떤 R에도 사용 가능하다.

---

2.1. TST with $R^2$ branching at root

root 노드에 $R^2$개의 자식 노드를 생성한 후, 각 자식 노드에 TST를 만든다.

즉, root노드에서 문자열의 맨 앞 2개 문자를 빠르게 탐색하는 전력이다.

이는 hashing보다 더 따른 성능을 보였다!!

TST vs Hashing

 

TST	Hashing
필요한 문자만 조사한다.	모든 문자를 조사한다.
문자열만 사용 가능하다.	hash function에 의해 성능 차이가 난다.
order operation을 지원한다.	order operation을 지원하지 않는다.

 

결론: TST가 더 빠르다!!

---

Character-based operations

Tries로 쉽게 구현할 수 있는 character-based operations에 대해 살펴보겠다.

1. Ordered iteration

"모든 key를 정렬된 순서대로 순회(=iterate)하는 연산"이다.

Algorithm

Inorder(left→mid→right)로 Trie를 순회한다.

• Root 노드부터 현재 노드까지의 경로의 문자 순서(=sequence of characters)를 유지한다.
• 현재 노드의 value가 non-null인 경우, 현재 노드까지의 문자 순서를 queue에 push한다.

2. Prefix match

"Input string을 prefix(=접두사)로 두는 모든 key를 구하는 연산"이다.

Algorithm

Input string을 key로 두는 노드를 탐색 연산으로 찾은 후,

(해당 노드를 root 노드로 두는) 서브 trie의 모든 key를 순회한다. (by ordered iteration)

3. Longest prefix

"Input string의 prefix(=접두사)인 가장 긴 key를 찾는 연산"이다. 

(=longest key that is a prefix of input string)

Algorithm

Input string을 key로 두는 노드를 탐색한다.

이때, null 노드 혹은 input string의 마지막 char 노드가 나올 때까지, 탐색 연산을 진행한다.

탐색 경로의 마지막 value 노드(=value가 non-null인 노드)의 key를 반환한다.