[자료구조] 트라이(Trie) 트리

 

 

트라이(Trie)

트리구조의 트라이

 

 

 

트라이(trie)는 탐색 트리의 일종으로 동적 집합이나 연관 배열을 저장하는데 사용하는 자료구조이다. 알고리즘 문제 등에서는 주로 문자열 저장 문제의 해결 방법으로 종종 등장한다.

문자열 검색을 빠르게 해주는 이진 탐색 트리의 구조로 한 레벨당 문자가 하나씩 저장되므로 문자열 검색 시 시간 복잡도는 O(NlogN)이다. 

 

 

출처 ; https://ko.wikipedia.org/wiki/트라이_(컴퓨팅)

위의 사진은 "A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이.

 

 

 

◎ 알고리즘

트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리이다. 

주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가며 만들어진다. 

 

탐색의 순서는 다음과 같다.

1. 탐색하려고 하는 문자열을 가져와 첫 번째 문자가 저장되어 있는지 체크한다. 

2. 현재 문자로 이루어진 노드가 존재하면 그 노드로 그 다음 문자열을 탐색하고 노드가 없으면 그 노드를 새로 할당받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다. 

 

 

 

 

 

 

참고 자료;

URL

ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

---