인프런 커뮤니티 질문&답변
작성한 질문수
3-N 보충 의견 드립니다
해결된 질문
작성
·
23
0
안녕하세요, 큰돌 선생님!
완전 이진 트리에 대한 설명에 대해 보충 의견 드리고자 글 남기게 되었습니다.
설명 중 "완전이진트리의 특징은 깊이가 3일 경우 2^3 - 1 = 7개의 노드를 갖는다" 라고 설명해주신 부분이 존재합니다.
다만 해당 특징은 완전이진트리 중에서도 포화이진트리에 대한 설명으로 알고 있습니다.
문제의 조건 중 2^k - 1 개의 노드를 갖는다는 조건이 존재하기 때문에, 단순한 완전이진트리가 아닌 포화이진트리가 되기 때문에 해당 문제의 해설이 성립될 수 있었던 것이라고 생각합니다.
혹시 제가 완전이진트리에 대한 개념이 잘못된거라면 지적 부탁드립니다! 감사합니다.
답변 2
0
안녕하세요 케이님 ㅎㅎ
좋은 말씀 정말 감사합니다.
설명변경 :: 문제에서 나오는 조건인 " K인 완전 이진 트리는 총 2K-1개의 노드"는 완전이진트리 중 하나인 포화이진트리에 속합니다. 완전이진트리는 트리의 모든 레벨이 노드로 꽉 차 있고, 마지막 레벨만 예외적으로 왼쪽부터 순서대로 채워지는 트리를 말합니다.
이런식으로 변경되었습니다.
다시 한번 감사하다는 말씀을 드립니다.
0
안녕하세요, 인프런 AI 인턴입니다. K케이님!
완전 이진 트리에 대한 개념은 혼동이 올 수 있는 부분인데요, 질문 주신 부분에 대해 설명드리겠습니다.
완전 이진 트리와 포화 이진 트리의 차이는 다음과 같습니다:
- 완전 이진 트리는 모든 레벨이 다 채워져 있지는 않지만, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 차례대로 채워져 있습니다.
- 포화 이진 트리는 모든 레벨에 노드가 꽉 차 있어야 하며, 노드의 개수가 정확히 ( 2^k - 1 )이어야 합니다. 따라서, 깊이가 3인 경우 ( 2^3 - 1 = 7 )개의 노드를 가지는 것이 포화 이진 트리에 해당합니다.
따라서 말씀하신 부분이 포화 이진 트리에 대한 설명이 맞습니다. 완전 이진 트리와 헷갈릴 수 있지만, 두 개념의 차이를 잘 이해하신 것 같아요.
유사한 사례를 가지고 있는 다른 질문들이 많아 아래의 답변 링크에서 더 많은 정보를 참고하실 수 있습니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.