인프런 커뮤니티 질문&답변
작성한 질문수
Trie 자료구조 관련 질문
해결된 질문
작성
·
36
0
김치찌개를 Trie 자료구조에 맞게 삽입하는 과정 중
"치" 노드의 값에 {"" : 0,"찌" : } 이렇게 들어가는 걸로 그림에서 보이는데 해시테이블은 키값 쌍 구조 아닌가요? 어떻게 두개의 쌍이 한 노드안에 들어가는지 이해가 안갑니다.
또한 {"찌" : value} 에서 저 value값에는 다음 노드의 주소값이 들어가는 건가요? 아니면 어떤 값이 들어가든 상관없나요?
상관없다면 키값으로만 연결되는 구조인가요?
답변 2
0
한 노드에 두개의 키가 들어갔다기 보다는 한 노드에 해시테이블이 한 개씩 존재한다고 보셔야합니다. 노드의 children 속성이 해시테이블을 나타냅니다.
해시테이블에는 여러개의 키와 값을 저장 할 수 있습니다.
'치'노드에는 키가 "*", "찌" 두 개가 존재하는 것이고 각 키에 맞게 값이 저장되어 있는 것입니다.
값으로는 다음 단어가 저장된 노드의 주소가 저장되지만, 하나의 단어가 완성됐다는 의미로 키 "*"와 값은 어떤 값이 와도 상관없으므로 0이라는 값을 넣어준 것입니다.
단어의 끝을 나타내는 "*"는 값이 필요없어서 어떤 값이 와도 상관없지만, 다음 글자를 나타내는 키에 해당하는 값은 다음 노드를 저장하고 있어야 합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 이재승님께서 Trie 자료구조에 대해 질문해 주셨습니다.
Trie 자료구조는 문자열을 효율적으로 저장하고 검색하기 위한 트리형 자료구조입니다. 각 노드는 여러 자식을 가질 수 있으며, 일반적인 Trie 구현에서는 각 노드가 해당 문자를 포함하는 자식 노드들의 정보를 가지고 있습니다. 보통 자식 노드를 나타내기 위해 해시테이블(map)을 사용하여 키-값 쌍으로 자식을 관리하며, 키는 다음 문자가 되고 값은 그에 해당하는 자식 노드로 연결됩니다.
Trie 노드의 해시테이블 구성: 질문하신 내용에서 “치” 노드의 해시테이블이
{"" : 0,"찌" : }로 보인 것에 관해 설명하자면, 일반적으로 키-값 쌍의 구조가 맞습니다. 첫 번째 항목은 빈 문자열 키와 0이라는 값이 있는 것으로, 이 값은 종종 끝점을 나타내는 플래그로 사용됩니다. 두 번째 항목인"찌"에 대한 값은 다음 노드의 포인터나 해당 지점의 정보가 들어갑니다.Value의 역할:
"찌"와 관련된 value는 보통 다음 노드의 참조(주소)로 사용됩니다. C++이나 Java와 같은 언어에서는 이 value가 노드를 가리키는 포인터일 것이며, Python과 같은 언어에서는 객체 참조일 수 있습니다. 트리의 탐색이나 노드 연결을 위해 이들의 주소나 참조가 저장되는 것입니다.키값 연결: Trie에서는 각 문자의 연결을 통해 단어가 완성되어 가기 때문에, 각 노드의 해시맵에서 키는 특정 문자를 나타내고, 그에 따른 값은 다음 문자로 이동하기 위한 연결입니다. 이런 구조 덕분에 효율적인 검색이 가능해집니다.
더 많은 이해를 돕기 위해 다음과 같은 관련 질문을 참고하시길 추천드립니다: Trie에 대한 이해 및 구현 방법.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.