retrieval tree

문자열에서 검색을 빠르게 도와주는 자료구조 정수형 이진탐색트리는 O(logN), 문자열에서는 최대길이 M일 때 O(M*logN). 트라이 활용 시, O(M) 가능 자동완성기능, 사전 검색 등 문자열 탐색에 특화됨 trie == radix tree = prefix tree == retrieval tree 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있어서 저장공간이 크다. Node = key + data + child L : 총 문자열의 수, M : 제일 긴 문자열의 길이일 때, 생성 : O(L*M) 탐색 : O(M) References https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Dat..