트라이(Trie) 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색등 문자열을 탐색하는데 특화 되어있는 자료구조 래딕스 트리(radix tree) or 접두사 트리 (prefix tree) or 탐색 트리(retrieval tree) 라고도 한다. 트라이는 retrieval 에서 나온 단어다. 트라이 장단점 장점 트라이는 문자열 검색을 빠르게 한다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 더 효율적이다. 단점 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장공간의 크기가 크다는 단점도 있다. 트라이의 생성 시간복잡도는 O(MxL): 탐색 시간복잡도 O(L) 가..