트라이 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다. 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 ..
