트라이(Trie) 문자열에서 검색을 빠르게 도와주는 자료구조이다. 정수형에서 이진탐색트리를 이용하면 시간 복잡도는 O(logN)이 나오게 된다. 문자열에서 적용했을 때, 문자열의 길이만큼 탐색을 진행해야 하기 때문에 길이를 M이라 하면 O(M*logN)이 걸리게 된다. 하지만 트라이 자료구조를 사용하게 된다면 시간복잡도를 O(M)에 끊을 수 있다. 다음 문자열 집합 {"rebro", "replay", "hi" , "high", "algo"} 를 트라이로 구현한 것이다. 그림에서 보면 알수 있듯이 문자열의 접두사에 대응되는 노드는 서로 연결된 트리이고 빨간 노드는 문자열의 끝을 의미한다. 트라이의 중요한 속성 중 하나는 root에서 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻..
