C로 쉽게 풀어쓴 자료구조 제7장 트리 연습문제

소개글

어려운 부분만 제가 직접 작성

목차

13. 다음의 최소 히프트리에서 답하라
(1) 2를 삽입하였을 경우, 히프 트리를 재구성하는 과정을 보여라.
(2) 삭제 연산이 한번 이루어진 다음에 히프를 재구성하는 과정을 보여라

14. 히프 트리가 비어 있는 상태에서 다음의 연산들을 차례대로 수행한 후의 최소 히프 트리의 모습을 그려라

15. 다음의 파일에 대하여 다음 물음에 답하라
(1) 위의 파일을 순차적으로 읽어서 최대 히프트리를 구성하라. 공백 트리에서 최대 히프트리가
만들어지는 과정을 보여라
(2) (1)에서 구성된 최대 히프 트리가 저장된 배열의 내용을 표시하라
(3) (1)에서 구성된 최대 히프 트리에서 최댓값을 제거한 다음 재정비하는 과정을 설명하라
(4) 위의 파일을 순차적으로 읽어서 최소 히프 트리를 구성하라. 공백 트리에서 최대 히프트리가
만들어지는 과정을 보여라
(5) (4)에서 구성된 최소 히프 트리가 저장된 배열의 내용을 표시하라
(6) (4)에서 구성된 최소 히프 트리에서 최솟값을 제거한 다음 재정비하는 과정을 설명하라

본문내용

(1) 2를 삽입하였을 경우, 히프 트리를 재구성하는 과정을 보여라.
2를 삽입한다.
부모노드 12보다 작으므로 교환한다.
그 위의 부모노드인 6과 또 비교해 역시 작으므로 교환한다.
와 과 같은 방식을 통하여 역시 부모노드로 올라가게 되어 최종적으로 삽입된 2는 이 트리에 루트가 된다.

(2) 삭제 연산이 한번 이루어진 다음에 히프를 재구성하는 과정을 보여라
삭제연산을 수행하면 루트인 2가 삭제된다.
마지막 노드에 있는 12가 루트노드가 된다
최소히프이므로 자식노드 3과 7중에 더 작은 값인 3과 교환을 한다.
과 같이 자식노드 중 더 작은 6과 비교 후 교환을 한다.
최종적으로 최소 히프트리를 충족한 형태.

14. 히프 트리가 비어 있는 상태에서 다음의 연산들을 차례대로 수행한 후의 최소 히프 트리의 모습을 그려라
insert(20), insert(12), insert(3), insert(2), delete(), insert(5), insert(16), delete(), insert(1), is_empty()

참고 자료

없음