자동완성 접두 검색을 위해 trie를 쓰려 합니다. 해시 테이블·정렬 배열과 메모리 비용을 어떻게 비교하나요?

trie는 키의 문자·바이트 경로를 공유해 접두 탐색을 표현하는 구조입니다. 키 길이에 따라 이동하고 공통 prefix를 활용할 수 있지만 노드·자식 포인터·인코딩에 따라 메모리 비용이 커질 수 있습니다.

동작 원리와 전제

각 노드에 큰 고정 alphabet 배열을 두면 빠르지만 희소 자식에 공간을 낭비합니다. map·정렬된 간선·압축 radix 경로를 사용하면 메모리를 줄이는 대신 조회·수정 비용이 달라집니다. 유니코드 code point·byte·정규화 단위를 정합니다.

선택과 실패 처리

접두 후보가 많으면 찾는 비용보다 결과 출력·랭킹이 지배적입니다. 상위 K 캐시를 둘 수 있지만 점수 갱신과 삭제·동점 규칙을 관리합니다. 정적 키 집합은 정렬 배열의 lower_bound 범위 탐색이 더 단순할 수 있습니다.

구체적인 사례와 검증

문자열이 매우 길고 공통 prefix가 거의 없으면 trie의 노드 수가 입력 문자 수에 가깝게 늘 수 있습니다. 작은 alphabet 배열을 노드마다 두는 단순 구현은 메모리가 크게 증가할 수 있어 압축 경로나 sparse child 표현을 검토합니다. 접두 검색이 빨라도 수십만 후보를 모두 반환하면 출력과 정렬이 병목입니다. 최대 결과 수와 ranking 규칙을 정하고, top-K 요약을 캐시하면 점수 감소·삭제 때 경계 밖 후보를 복구할 구조가 필요합니다. 대소문자·정규화 정책은 저장과 검색이 같아야 하며 UI에서 같아 보이는 문자열을 무조건 같은 바이트로 가정하지 않습니다.

긴 공통 prefix·다국어·빈 키·삭제·큰 후보 집합을 시험합니다. 노드 수·바이트·조회 p99·업데이트 비용을 비교합니다. trie의 이론적 탐색 단계뿐 아니라 실제 메모리 locality와 출력량을 포함해야 합니다.