Trie
Learning Goals
- 데이터 구조에 대해 자세히 알아보기
- Trie로 작업하기
Background
방금 개를 구하고 이름을 정하고 있다고 상상해 보세요. 가장 인기 있는 개 이름 약 150개의 목록이 포함된 파일을 온라인에서 찾았습니다! 당신은 당신이 고려하고 있는 이름이 이 목록에 있는지 여부가 궁금합니다. trie는 데이터 조회에 적합하므로 trie.c에서 (거의!) 완전한 코드를 제공했습니다. 아직 구현되지 않은 check라는 함수가 하나 있습니다. 당신의 임무는 이 기능을 완료하는 것입니다.
Demo
Getting Started
- GitHub 계정을 사용하여 cs50.dev에 로그인합니다.
- 터미널 창 내부를 클릭하고 cd를 실행합니다.
- 코드 공간에서 Bottomup.zip이라는 zip을 다운로드하려면
wget https://cdn.cs50.net/2022/fall/labs/5/trie.zip 실행한 다음 Enter 키를 누르세요. wget과 다음 URL 또는 해당 문제에 대한 다른 문자 trie.zip 사이의 공백을 간과하지 않도록 주의하세요! - 이제 unzip trie.zip을 실행하여 trie이라는 폴더를 만듭니다.
- 더 이상 ZIP 파일이 필요하지 않으므로 rm trie.zip을 실행하고 프롬프트에서 "y" 다음에 Enter를 입력하면 됩니다.
Implementation Details
트라이 자체는 node라고 불리는 여러 구조체를 창의적으로 사용하여 구현된다는 점에 유의하세요. 트라이의 각 노드에는 크기 26의 (잠재적) 자식 배열이 있습니다. 즉, 알파벳 문자마다 하나의 잠재적 자식이 있습니다! 이 트라이에 단어를 추가하면, 단어의 모든 문자에 대해 부모가 루트 노드(첫 번째 문자의 경우)이거나 이전 문자(첫 번째 문자가 아닌 경우)인 새 노드 하위를 생성한다는 점에 유의하세요. 맨 마지막 문자에서 하위 노드의 is_word 속성을 true로 설정했습니다. 이제, 트라이에 단어가 있는지 확인하는 것은 트라이를 통해 해당 단어의 각 문자를 따라가는 것만큼 쉽습니다. 마지막 문자에 도달하여 is_word가 참이라는 것을 확인하면 그 이름이 우리 트리에 있는 것입니다!
Hints
- 아마도 노드 포인터, 커서를 트라이의 루트로 설정하여 시작하고 싶을 것입니다.
- 인수 단어의 모든 문자를 반복하면서 해당 문자에 해당하는 배열 인덱스를 결정합니다.
- 문자의 색인을 사용하여 children[index]가 NULL 포인터인지, 즉 해당 단어가 트라이에 존재하지 않는지 확인할 수 있습니다.
- children[index]가 실제로 노드인 경우 커서를 이 노드로 재설정하고 해당 하위 노드에서 다음 문자를 확인할 수 있습니다.
- 조회 시 대소문자를 구분해야 한다는 점을 기억하세요. 예를 들어, A와 a는 0에 대응하고, B와 b는 1에 대응해야 합니다.
생각해보기
언제 트라이를 데이터 구조로 사용하고 싶습니까? 언제는 안 될까요?
