Trie란 무엇인가요?

트라이(trie, "try"라고 발음하며 retrieval의 약자)는 문자별로 문자열을 저장하고 검색하기 위해 구축된 트리 모양의 데이터 구조입니다. 트리의 모든 간선(edge)은 단일 문자로 레이블이 지정되며, 루트에서 표시된 노드까지 내려가는 모든 경로는 저장된 하나의 단어를 형성합니다.

이러한 구조 덕분에 접두사(prefix) 관련 질문을 매우 빠르게 처리할 수 있습니다. 트라이에 "car"로 시작하는 단어가 있는지 확인하는 것은 수천 개의 단어가 저장되어 있더라도 루트에서 단 세 번의 문자 조회만으로 가능합니다. 트라이는 자동 완성, 맞춤법 검사, IP 라우팅 테이블과 같은 기능의 핵심 엔진입니다.

트라이의 각 노드(node)는 두 가지 상태를 가집니다:

• children: 문자에서 다음 TrieNode로 연결되는 맵(map)입니다.
• isEndOfWord: 루트에서 이 노드까지의 경로가 삽입된 전체 단어를 형성할 때 true가 되는 플래그입니다.

트라이의 다섯 가지 주요 연산은 다음과 같습니다:

1. Insert: 단어를 추가하며, 과정 중에 누락된 노드를 생성합니다.
2. Search: 전체 단어가 저장되어 있는지 확인합니다.
3. StartsWith: 주어진 접두사로 시작하는 저장된 단어가 있는지 확인합니다.
4. Delete: 단어를 제거하고 더 이상 사용되지 않는 가지를 정리(prune)합니다.
5. WordCount: 저장된 서로 다른 단어의 개수를 셉니다.

이제 Trie 클래스를 만들어 봅시다!