shine_hyun shine_hyun

Trie 구조 문자열을 쉽게 탐색하기 위한 tree형태의 구조 예를들어, 문자열 [Joe,John,Johnny,Jane,Jack]로 트라이 구조를 만들었을때이다. 이 트라이 구조는 최대 장점은 '검색'에 있다. [Joe,John,Johnny,Jane,Jack] 에서 'Joe'의 유무를 찾으려면 단순하게는 문자열 전체를 search해야한다. 찾으려는 문자 길이를 m, 문자열 길이를 n이라하자. 각 문자열에 character를 J,o,e와 하나씩 비교해야하고, 이것을 n번 반복하니 총 O(nm)의 복잡도가 발생한다. 반면 trie구조를 사용하면, 문자 길이 m인 O(m) 의 복잡도면 충분하다. Trie 구조는 내가 생각하기엔, 딱히 tree구조와 다른것은 없어보인다. 다만, 문자가 끝나는 것을 알려줘야하기 ..