Trie는 문자열을 빠르게 찾는 마법의 표가 아니라, 접두 경로를 노드로 공유하는 인덱스입니다. 그러므로 경로를 찾는 비용과 그 아래 결과를 열거하는 비용, 그리고 각 노드가 지불하는 메모리를 분리해 판단해야 합니다.
공통 접두 문자열 기반 키 수집
키가 car, cart, cat일 때 ca로 시작하는 모든 후보를 찾는다고 합시다.
구체적으로 findPrefix("ca")는 루트→c→a 두 간선을 찾은 뒤 멈춥니다. 이후 car, cart, cat을 반환하려면 하위 terminal을 방문하고 결과를 직렬화해야 하므로 총 비용은 접두 길이만으로 끝나지 않습니다. 자동완성처럼 최대 10개만 필요하면 방문 중 조기에 멈추고, 사전순이 아니라 점수순이면 별도 ranking 구조가 필요한지 먼저 정합니다. 해시 테이블은 전체 키의 동등 조회에 맞지만 접두 검색에는 별도 인덱스가 필요합니다. Trie는 문자나 바이트를 간선으로 삼아 공통 접두 경로를 공유합니다.
ca까지 두 단계를 내려간 뒤 그 하위 키를 모으면 됩니다. 하지만 접두 노드까지 빠르게 찾았다고 결과 수만큼 읽고 출력하는 비용까지 사라지지는 않습니다.
경로 존재와 키 종료의 구분
그림을 글로 읽기
- 루트
- c
- ca
- car · terminal
- cat · terminal
- cart · terminal
- 루트 → c: c
- c → ca: a
- ca → car · terminal: r
- ca → cat · terminal: t
- car · terminal → cart · terminal: t
ca 경로는 존재하지만 저장한 완성 키가 아닙니다. 반대로 car는 terminal이면서 자식 t도 있습니다. car를 삭제할 때 그 노드를 통째로 없애면 cart도 잃습니다. terminal 표시를 지운 뒤 자식이 없고 다른 키도 사용하지 않는 경로만 회수해야 합니다.
| 조회 | 경로 존재 | 완성 키 존재 | 접두 결과 |
|---|---|---|---|
| ca | 예 | 아니오 | car, cart, cat |
| car | 예 | 예 | car, cart |
| cab | 아니오 | 아니오 | 없음 |
| 빈 문자열 | 루트 | 빈 키 저장 정책에 따라 | 전체 후보 |
검색과 삽입의 기본 연산
findPrefix(prefix):
node = root
for unit in normalizeAndSplit(prefix):
node = node.children.get(unit)
if node is absent: return absent
return node
insert(key):
node = root
for unit in normalizeAndSplit(key):
node = node.children.getOrCreate(unit)
node.terminal = true
자식 조회가 O(1)이라는 전제에서 길이 L의 접두 노드 탐색은 O(L)입니다. 자식을 정렬 배열로 저장하면 노드별 이진 탐색 비용이 들어갈 수 있습니다. 후보 열거는 방문 노드와 출력 문자열 총량에 비례하며, 매번 문자열을 복사하면 추가 비용이 생깁니다.
동시 삽입은 같은 경로의 중복 노드를 만들거나 불완전 경로를 공개하지 않도록 해야 합니다. 잠금·불변 경로 복사·단일 writer 중 실제 구조에 맞는 방법을 선택합니다. 노드 삭제 후 참조를 가진 독자의 수명도 별도입니다.
자식 표현과 메모리 비용
| 자식 표현 | 이점 | 비용 |
|---|---|---|
| 고정 alphabet 배열 | 빠른 직접 접근 | 자식이 적어도 큰 배열 보유 |
| 해시 맵 | 희소한 자식 수에 비례 | 해시·할당·부가 메모리 |
| 정렬 간선 배열 | 작은 연속 저장·지역성 | 검색·삽입 이동 |
| 압축 radix 경로 | 외길 노드 묶음 감소 | 간선 문자열 비교·분할·병합 |
공통 접두사가 거의 없으면 노드 수는 모든 키 길이 합에 가까워질 수 있습니다. 한 노드마다 256개 포인터를 두면 실제 문자 하나당 큰 메모리를 씁니다. 노드 개수뿐 아니라 포인터·맵 용량·문자열 조각의 소유와 allocator 비용까지 계산해야 합니다.
압축 경로 cart에 car를 넣으면 중간 위치에서 간선을 분할하고 그 지점에 terminal을 만들어야 합니다. 단순히 노드를 줄이는 최적화가 아니라 삽입·삭제 알고리즘도 바뀌는 구조입니다.
문자열 단위·정규화 정책의 고정
같아 보이는 유니코드 문자열도 바이트열과 코드 포인트열이 다를 수 있습니다. 저장과 검색에서 같은 정규화·대소문자 정책을 사용해야 같은 경로를 찾습니다. 바이트 Trie와 코드 포인트 Trie는 노드 수와 alphabet 크기가 다릅니다. 사용자 언어의 정렬 순서까지 필요하면 단순 바이트 간선 순회와 다를 수 있습니다.
정규화가 서로 다른 원본 키를 같은 키로 합치는 경우에는 원본 표시 문자열과 식별 규칙을 분리합니다. 접두 검색이 권한을 우회하지 않게 테넌트·공개 범위도 후보 수집과 반환에 적용합니다.
탐색 비용과 결과·순위 비용
a 아래 후보가 백만 개라면 findPrefix("a")까지는 접두 길이에 비례해 끝나도, 그 노드의 모든 자손을 모아 정렬하고 반환하는 비용은 결과 수에 따라 커집니다. 먼저 최대 K개만 필요한지, 사전순인지 점수순인지 정하고, 점수순 top-K를 노드마다 요약해 둘 때는 점수 감소나 삭제로 현재 K 밖 후보가 다시 올라오는 경우를 갱신해야 합니다.
정적 키 집합에서는 정렬 배열에서 a로 시작하는 첫 위치와 끝 위치를 이진 탐색한 뒤 그 범위만 순회하는 편이 더 단순할 수 있으므로 키 수·길이·공통 접두 비율·갱신률·결과량으로 비교합니다.
시험은 빈 키, car 삭제 후 cart 보존, 긴 공통 접두, 다국어 정규화, 큰 결과 집합과 동시 삭제를 포함해야 합니다.