자료구조/비선형 자료구조
[비선형 자료구조] 트라이(Trie)
트라이(Trie) 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조이다. Prefix Tree, Retrieval Tree, Digital Search Tree 라고도 부른다. 정렬된 트리구조다. 문자열같은 것들을 트라이에 구축을 해둬야하기 때문에 문자열 저장을 위한 메모리가 (많이)필요하지만 탐색이 빠르다. 길이가 N개인 문자열 탐색의 시간복잡도는 O(N)이다. 대신 사전에 이런 문자열들을 이 트라이 형태로 구축을 해야하는데 구축할 때 드는 생성시 시간복잡도는 트라이에 넣으려는 문자열의 개수가 M개라고 할 때 O(MN)이다. 하지만 한번 구축하면 탐색할 때 굉장히 빠르다는 장점이 있다. 동일 위치에서의 공통 부분들은 중복해서 들어가지는 않지만 다른 부분에 대해서는 트라이를 적용시켜줘야 하기 ..
