Trie와 문자열 자료구조

오늘은 Trie, 트라이라고 불리는 자료구조를 배워보겠습니다.

이름은 영어 retrieval, 검색이라는 단어에서 따왔어요.

그림 왼쪽을 보시면 접두사 공유라는 박스가 있죠.

cat, car, card 세 단어가 c와 a라는 경로를 함께 사용하고 있어요.

이것이 Trie의 핵심 원리입니다.

가운데 트리 구조를 보면, 루트에서 시작해 한 글자씩 내려갑니다.

초록색 별표가 붙은 노드는 단어의 끝을 뜻해요.

예를 들어 t 노드에 별이 있으면 cat이라는 단어가 완성된 거죠.

오른쪽 주황색 상자를 보시면 시간복잡도 비교가 있습니다.

Trie에서 검색 시간은 O(L)이에요. L은 문자열의 길이입니다.

해시맵도 평균 O(L)이지만, 해시 충돌이 생기면 느려질 수 있어요.

이진 탐색은 O(L 곱하기 log N)으로, 전체 단어 수 N에 영향을 받죠.

Trie만이 전체 단어 수와 상관없이 항상 O(L)을 보장합니다.

그런데 Trie의 진짜 강점은 정확한 검색이 아니에요.

접두사로 시작하는 모든 단어를 빠르게 찾는 것이 핵심이죠.

해시맵은 완전히 일치하는 키만 찾을 수 있어요.

하지만 Trie는 ca로 시작하는 단어를 모두 쉽게 수집할 수 있습니다.

이 점이 자동완성이나 맞춤법 검사에 Trie가 필수인 이유예요.

하단의 범례를 보면, 별표는 isEnd가 true인 노드를 뜻합니다.

각 노드가 children이라는 딕셔너리로 자식을 관리하는 구조예요.

메모리는 알파벳 크기 곱하기 전체 문자 수에 비례합니다.

영어 소문자만 쓰면 알파벳 크기가 26이라 관리할 만해요.

정리하면, Trie는 접두사 공유로 메모리를 아끼면서 빠른 검색을 보장하는 트리 자료구조입니다.