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

우선 Trie Tree를 설명하기 전에  Binary Search Tree(이진탐색 트리)를 이용해 문자열을 사용한다 가정하면 기본 이진트리의 검색 시간인 O(log n)과 더불어 각 노드에 들어 있는 문자열(문자열의 최대길이를 M이라 가정)을 찾는 시간 O(M log n)의 시간이 걸린다. 

그래서 이 문제를 해결하기 위해 사용하는 것이 Trie tree이다.

 

Trie Tree

이 트리의 경우 node에 문자열을 한자씩만 저장한다.

문자열이 다 같은 문자로 시작하는게 아니기에 Root node의 경우 비워준다. 

모든 노드는 최대 26개의 노드를 허용한다. (알파벳이 26개) 단, 대, 소문자 구별시 더 길어진다. 

시간 복잡도는 O(M)이된다. (M은 문자열의 최대 길이)

 

 

참고자료

 

https://www.youtube.com/watch?v=TohdsR58i3Q&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=4