> 트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 래딕스 트리(radix tree) 나 접두사 트리(prefix tree)라고도 한다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것이다. 우리는 문자열 검색을 개선하기 위해 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있다. 트라이라는 명칭은 Retrieval에서 유래한다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득ㅇ ㅣ디ㅗㄴ다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리할까? 아래 그림은 문자열 집합 ..