트라이를 사용하는 이유는 무엇인가?

문자열 검색 속도를 문자열 길이만큼으로 줄이기 때문이다. 키 전체를 비교하지 않고 문자 경로를 따라가며 빠르게 찾는다.

해시 맵은 평균적으로 O(1)이지만 최악의 경우 충돌로 인해 성능이 떨어진다. 반면 트라이는 최악의 경우에도 문자열 길이인 O(L)을 보장한다.

공통 접두사를 공유하는 구조 덕분에 자동 완성이나 사전 검색 기능 구현에 최적화되어 있다.