트라이
트라이은 문자열의 각 문자 또는 비트를 간선으로 표현하고 접두사를 공유하는 트리 구조다 문자열 색인 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할...
| 분류 | 자료구조 · 문자열 색인 자료구조 |
|---|---|
| 목적 | 문자열의 각 문자 또는 비트를 간선으로 표현하고 접두사를 공유하는 트리 구조다 |
| 처리 방식 | 루트에서 입력의 문자 순서대로 간선을 따라 내려가며 필요한 노드를 생성한다 |
| 복잡도·성능 | 길이 L의 키 삽입·검색 O(L), 저장은 서로 다른 접두사 수에 비례 |
| 필수 조건 | 문자 집합과 종료 표시 및 노드의 자식 저장 방식이 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
트라이은 문자열의 각 문자 또는 비트를 간선으로 표현하고 접두사를 공유하는 트리 구조다 문자열 색인 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 루트에서 입력의 문자 순서대로 간선을 따라 내려가며 필요한 노드를 생성한다. 종료 표시로 어떤 노드에서 완전한 단어가 끝나는지 기록하고 접두사 검색은 해당 경로의 존재를 확인한다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 길이 L의 키 삽입·검색 O(L), 저장은 서로 다른 접두사 수에 비례 올바르게 적용하려면 문자 집합과 종료 표시 및 노드의 자식 저장 방식이 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 자동 완성·사전 검색과 XOR 최댓값 탐색 등에 사용한다. 메모리 사용량은 자식 배열·해시맵 선택에 크게 좌우된다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]