트라이

트라이 (Trie), 때로는 접두사 트리(prefix tree)라고도 불리는 것은 키가 대부분 문자열인 동적 집합 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료 구조입니다. 일반적인 이진 검색 트리와 달리, 트리의 노드들은 키와 직접적으로 연관되어 있지 않습니다. 대신, 노드의 위치가 해당 노드와 연관된 키를 정의합니다. 루트부터 특정 노드까지의 경로는 해당 노드와 연결된 키를 형성합니다. 하나의 노드의 모든 자손은 해당 노드와 연결된 문자열의 공통 접두사를 공유하므로 "접두사 트리"라는 이름이 붙었습니다.

주요 특징:

• 접두사 기반 검색: 트라이는 문자열의 접두사를 기반으로 검색하는 데 매우 효율적입니다. 특정 접두사를 공유하는 모든 키를 빠르게 찾을 수 있습니다.
• 공간 효율성: 여러 키가 공통 접두사를 공유하는 경우, 트라이는 이러한 접두사를 공유함으로써 공간을 절약할 수 있습니다.
• 삽입 및 삭제: 키의 삽입 및 삭제 연산은 일반적으로 O(m) 시간에 수행됩니다. 여기서 m은 키의 길이입니다.
• 알파벳 크기 의존성: 트라이의 성능은 알파벳의 크기에 따라 달라집니다. 알파벳이 클수록 각 노드가 더 많은 자식을 가질 수 있으므로 공간 사용량이 증가할 수 있습니다.

활용 분야:

트라이는 자동 완성, 맞춤법 검사, IP 라우팅 (최장 접두사 매칭), T9 사전, 데이터 압축 등 다양한 응용 분야에서 사용됩니다. 또한, 문자열 검색 알고리즘의 일부로 사용되기도 합니다.

구현:

트라이는 일반적으로 노드 클래스를 사용하여 구현됩니다. 각 노드는 자식 노드를 가리키는 포인터 (알파벳 크기에 따라 배열 또는 해시 테이블로 구현될 수 있음)와 해당 노드가 키의 끝을 나타내는지 여부를 나타내는 플래그를 포함합니다.