[CS] 트라이(trie)

트라이(trie)

문자열의 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조

 

각 Trie의 노드는 <Key, Value> 형태의 Map을 가지고 있다. 여기서 Key는 하나의 알파벳이 되고, Value는 Key에 해당하는 자식 노드가 된다.

루트 노드는 비어있고, 자식 노드를 가지고 있다.

 

예를 들어, DOG, CAR, CAT, COW라는 단어로 이루어진 Trie를 도식화하면 아래와 같다. 만약, 'CAT'이라는 문자열을 찾으려면, 루트 노드에서부터 차례대로 root -> [C] -> [A] -> [T] 를 탐색한다.

 

 

• 정렬된 트리 구조이다.
  (데이터에 따라 이진트리일 때도 있다)
• Trie는 자식노드를 맵<key, value> 형태로 가지고 있다.
  
• 루트를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다.
• 루트 노드는 빈 문자와 연관 있다.
  (특정 문자가 할당되어있지 않다)

 

트라이(Trie) 장단점

• 트라이(Trie)는 문자열 검색을 빠르게 한다.
• 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다.
• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. (예를 들어, 알파벳에 대해 트리를 형성해야 한다면 a~z 인 총 26개의 포인터 배열을 가지고 있어야 한다. 즉, 최종 메모리는 O(포인터 크기 * 포인터 배열의 개수 * 트라이에 존재하는 총 노드의 수) 가 된다.)

 

---

 

문자열 5개 {"blog", "he", "her", "supreme", "superm"} 이 있다고 가정해보자. 트라이는 이때 아래와 같은 트리를 형성하게 된다.

 

루트 노드가 되는 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

superm 은 s → su → sup → supe → super → superm 으로 이루어지는데 이 과정에서 나타난 것들은 모두 superm 의 접두사이다.

 

 

 

https://hibee.tistory.com/306

https://frtt0608.tistory.com/115