트라이 (Trie)

한 줄 정의: 문자열들을 저장할 때 공통으로 시작하는 접두사를 트리의 같은 경로로 공유하도록 구성한 트리 형태의 자료구조입니다.

쉽게 풀면

사전을 상상해 보세요. "사과", "사슴", "사람"은 모두 '사'로 시작하니 같은 서랍에서 시작해서, 다음 글자('과', '슴', '람')에 따라 서랍 안 칸이 갈라집니다. 트라이는 바로 이런 식으로, 문자를 한 글자씩 따라가며 가지를 뻗는 나무 구조입니다. 검색창에 "사"만 입력해도 "사과", "사슴", "사람"이 후보로 뜨는 자동완성 기능이 바로 트라이 구조 덕분에 가능합니다.

왜 중요한가

대량의 문자열을 다루는 시스템에서는 저장된 항목 수와 무관하게 빠른 검색 속도를 유지하는 것이 중요한데, 트라이는 이런 요구를 만족시키는 대표적인 자료구조이기 때문에 검색엔진, 자연어처리, 네트워크 시스템 논문에서 성능 최적화의 근거로 자주 언급됩니다.

논문에서는 이렇게 쓰입니다

"자동완성 기능을 구현하기 위해 사전에 등록된 모든 단어를 트라이(trie) 구조로 저장하여 접두사 검색 시간을 단어 길이에만 비례하도록 하였다."

이 문장은 저장된 단어 수가 아무리 많아도, 검색하려는 단어의 글자 수만큼만 트리를 따라 내려가면 되므로 검색 속도가 매우 빠르게 유지된다는 성능상의 장점을 설명하고 있습니다. 자연어 처리, 문자열 검색, IP 라우팅 테이블 등에서 널리 활용됩니다.

"네트워크 패킷의 목적지 주소를 처리하기 위해 이진 트라이 기반의 라우팅 테이블을 구성하여 최장 접두사 매칭을 수행하였다."

네트워크 라우터에서 IP 주소 검색에 트라이 구조를 활용한 시스템 분야의 예문이다.

"철자 교정기 구현을 위해 어휘 사전을 트라이로 인덱싱하여 편집 거리 기반 후보 단어 탐색 범위를 효율적으로 줄였다."

자연어처리 응용에서 트라이를 활용해 탐색 범위를 줄이는 예문이다.

조금 더 깊게 보면

표준 트라이는 각 노드가 알파벳 크기만큼의 자식을 가질 수 있어 저장 항목이 적을 때는 메모리 효율이 떨어질 수 있는데, 이를 개선한 형태로 경로를 압축하는 패트리시아 트라이(radix trie)나 접미사 트리 등이 활용됩니다. 논문에서는 삽입·검색 시간복잡도뿐 아니라 실제 메모리 사용량과 캐시 효율성까지 함께 비교하는 경우가 많습니다.

주의할 점

트라이는 값의 대소 비교를 기준으로 가지를 나누는 이진탐색트리와 달리, 문자열의 글자 하나하나를 기준으로 가지를 나눈다는 점에서 근본적으로 다른 구조입니다. 저장하는 단어 수가 적고 접두사 공유가 거의 없다면 트라이가 오히려 메모리를 더 많이 차지할 수도 있습니다.