음하하하

Trie

<소개>

single string word로 이루어진 dictionary를 만든다고 가정

set<string> 대신 tries를 사용하는 이유?

1. trie는 string을 insert 하거나 find 할 때, O(L)의 시간으로 가능하다. (L : length of single word)

2. set<string> 이나 hash table은 정확한 word만 찾을 경우에만 사용이 가능하다.

하지만  trie는 예외의 경우가 있다.

- 한 글자만 다른 word를 찾을 때

- 공통 prefix가 있는 word를 찾을 때

- 한 글자가 빠진 word를 찾을 때

etc...

<Trie 란?>

retrieval 에서 따온 말

다음과 같은 자료구조로 되어 있다.

1. trie는 tree의 종류 중 하나로, 각각의 vertex는 하나의 word나 prefix를 나타낸다.

2. root는 empty string ("") 을 나타냄

3. 임의의 vertex가 root로 부터 K개의 edge 만큼 떨어져 있으면, 길이 K의 prefix를 나타낸다.

4. V와 W가 trie의 vertex이고 V가 W의 direct father이면,

V는 W의 associated prefix를 반드시 가지고 있다.

<coding>

- find exactly matched word

- 4 functions

1. addWord        - add a single string word to the dictionary

2. countPreffixes - dictionary 내의 특정 prefix를 갖는 모든 word의 수를 반환

3. countWords    - dictionary 내의 특정 word(인풋으로 주어짐)의 개수를 반환

4. 알파벳만 지원