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

1. 트라이

탐색 트리의 일종이며, 동적 집합이나 연관 배열을 저장하는데 사용되는 트리 자료구조이다. 문자열을 저장하고 효율적으로 탐색하기 위한 자료구조로 생각하면 된다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산됨을 의미한다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 메모리에 최적화된 경우에는 기수 트리가 된다. 

"A", "to", "tea", "ted", "ten", "i", "in", "inn"을 키워드로 둔 트라이

 

 

2. 장단점

• 문자열 검색 시 빠른 검색 가능
• 문자열 탐색 시 하나씩 전부 비교하는 것 보다 시간 복잡도 측면에서 효율적
• 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있으므로 공간적인 측면(메모리)에서는 비효율적

3. 구현

키의 길이가 m일 때 탐색, 삽입 모두 O(m) 시간에 수행된다.

트라이의 자세한 구현사항은 이곳을 참조한다.

---

참고문서

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie

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

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

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전