# Trie - Trie 는 문자열의 탐색에 유용한 자료구조다. $L$ 이 문자열의 전체 길이라고 가정했을 때, 문자열이 존재하는지 확인하기 위해서는 $O(L)$ 의 시간밖에 걸리지 않는다. - 문자열을 처리하는 방법에는 2가지가 있다. 첫번째는 Hash를 사용하는 방법이고, 두번째가 Trie를 사용하는 방법이다. Hash 로 처리하면 문제열을 찾는데 필요한 시간은 평균적으로는 $O(1)$ 이고, 최악의 경우에는 $O(N)$ 이다. 만약에 Trie 를 사용한다고 하면, 평균이나 최악이나 모두 $O(L)$ 만큼의 시간복잡도가 걸린다. - Trie를 구현할 때는 분기가 되는 문자의 종류 크기의 배열이 필요하고, 그 배열에는 다음 child를 가리키는 노드의 포인터가 저장된다. 따라서, 분기가 되는 문자의 종류가 다양하게 분포되어 있지 않다면 불필요한 메모리가 낭비될 수 있다는 단점이 있다.