문자열 - 트라이

[1. 개요]

트라이(trie) 는 문자열의 집하을 표현하는 트리 자료구조로

M 이 모든 문자열의 최대 길이일 때.

원하는 원소(문자열)를 O(M) 시간내에 찾을 수 있다.

 

트라이의 루트는 항상 길이 0인 문자열에 대응 되며

노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1 씩 늘어난다.

 

특성

1. 종료 노드는 해당 위치에 대응되는 문자열이 트라이가 표현하는 집합에 포함되어 있다는 것을 의미한다.
2. 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻는다.
3. 각 노드에 대응되는 문자열을 저장하지 않는다.

---

[2. 트라이 노드]

트라이 노드는 보통 다음과 같이 구성된다.

1. 자손 노드를 가리키는 포인터 목록
   => 입력에 등장 할 수 있는 모든 문자에 대응되는 원소를 갖는 고정 길이 배열
   => 메모리 사용량은 다소 높지만, 다음 노드를 찾는 과정을 O(1) 만에 할 수 있다.
   
   
2. 이 노드가 종료 노드인지 아닌지를 나타내는 boolean 변수
   => 이 노드 까지 오면서 만난 문자를 모으면,

---

[3. 구현]

 

---

[4. 응용]

문자열을 key 로 하는 std::map<std::string, int> 을 대체 할 수 있다.

•  trie node 에서 teriminal 값을 int 로 대체
•