코딩못하는사람

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리가 검색을 할 때 자동으로 완성시켜주는 단어들을 보면 트라이가 사용된 예입니다. 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간복잡도를 갖고 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이의 형태 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} 가 존재할 때 트라이의 예입니다. 다음과 같은 모양으로 트리를 만들어서 연산을 문자열의 길이만큼하는 시간복잡도를 갖게하는 것입니다. 이에 따라 트리의 특징은 시간이 O(M)..