Trie

단어 검색에 최적화된 Tree 기반의 자료구조이다.

root에서 부터 현재 목록에 있는 모든 단어에 대한 글자별로 트리를 구성함으로서 단어검색을 최적화 하는 자료구조이다.

시간복잡도

단어의 개수 : N
단어의 길이 : M

먼저 해당 Trie 자료구조를 구성하는데 O(N * M) 이 소요된다.

하지만 Trie 가 빛을 발할 때는 단어검색을 할 때인데, 일반 완전탐색으로 문자열을 찾으려면 O(n * m) 의 시간복잡도가 필요하지만, Trie 자료구조는 O(M) 이 소요된다.

그러므로 한번만 만들어놓으면 검색하는데 계속 활용할 수 있다는 것이다.

데이터 삽입

먼저 root 부터 내려오면서 단어의 첫글자부터 계속 노드를 추가해준다. 만약 글자가 끝났다면, asterisk(*) 를 추가해주어서 해당 단어가 끝이 났음을 명시해주어야 한다.

데이터 검색

루트에서부터 검색하려는 단어를 한글자씩 찾으며 트리를 내려온다. asterisk를 만날때까지 해당 단어를 만들어내지 못한다면, 그 단어는 없는 것이다.

혹은 검색하는 단어의 끝까지 도달했는데 트리에서 찾아내지 못했다면, 그 단어는 존재하지 않는 단어이다.