2018 7급 국가직 기출풀이 - 자료구조론 마형 7번

문제 풀이에 앞서,

안녕하세요. 오늘은 2018년 7급 국가직 자료구조론 마형 7번의 문제풀이를 들고 왔습니다.

제 풀이는 문제순으로 진행되지 않으니, 혹시나 중간에 궁금하신 문제에 대해서는 방명록에 요청해주시면 됩니다.

그리고 항상 하는 말이지만, 퍼가는 것은 허락되나 제발 제가 피드백을 받을 수 있게 원글 링크를 걸어주세요~!

그리고 피드백을 저에게 달라고 해주시면 감사하겠습니다♡

---

문제

문7. 다음 키(key) 값을 갖는 9개의 데이터를 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 루트 노드를 삭제한 후 구성되는 이진 탐색 트리에 대한 설명으로 옳지 않은 것은?

5, 6, 2, 8, 4, 1, 9, 3, 7

 

① 모든 노드들의 차수(degree)들의 합은 7이다.

② 모든 단말 노드들의 키 값들의 합은 21이다.

③ 중위 순회(inorder traversal)할 경우 키 값이 1, 2, 3, 4, 6, 7, 8, 9인 노드들을 순서대로 방문한다.

④ 루트 노드의 키는 4와 6중 한 개의 값을 가진다.

---

정답

2번

---

풀이전 기초

* 이진 탐색 트리 (binary search tree)

- 모든 노드의 키는 유일하다.

- 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

- 오른쪽 서브 트리의 키들은 루트의 키보다 작다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 즉, 위 조건을 만족해야 한다.

 

* 이진 탐색 트리의 루트를 삭제할 경우

- 새로운 루트 노드의 키 값 :

   왼쪽 서브트리에 있는 값 중 가장 큰 값 or 오른쪽 서브 트리에 있는 값 중 가장 작은 값

- 이유 : 트리의 변동성을 최소화하기 위해서

 

* 중위 순회(inorder traversal) 방식

- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회

- 이런 방식으로 이진 탐색 트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다.

---

풀이과정

우선 보기에 쓰여진대로 이진 탐색 트리를 작성해 봅시다.

손재주가 없어서 발로 만든 자료입니다T^T 감안해서 봐주세요.

녹색의 숫자는 순서입니다.

[ 깨뱌 자체 제작 자료]

 

[ 깨뱌 자체 제작 자료]

[ 깨뱌 자체 제작 자료 ]

[ 깨뱌 자체 제작 자료 ]

[ 깨뱌 자체 제작 자료 ]

---

자 처음으로 완성된 이진 탐색 트리는 이런 모양이 됩니다.

그 다음 문제에서 루트 노드를 삭제하겠다 했습니다.

위의 풀이전 기초에서 루트 노드 5를 삭제 할 경우에 따라 다음 루트는 4 또는 6이 됩니다.

그래서 4번은 맞는 보기입니다.

---

루트 노드 5를 삭제한 경우 이진 탐색 트리를 다시 구성해 보았습니다.

[ 깨뱌 자체 제작 자료 ]

여기서 차수는 모든 가지수를 말하므로 차수(degree)는 7이 됩니다. 따라서 1번은 맞는 보기입니다.

---

중위 순회의 경우는 풀이전 기초에서 설명한 글에 따라

두가지 모두 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 인 노드들을 순서대로 방문합니다.

따라서 3번도 맞는 보기입니다.

---

단말 노드들은 자식이 없는 노드들을 말합니다.

이 문제의 경우 단말 노드들의 합은 1 + 3 + 7 + 9 = 20 입니다.

따라서 2번 보기가 틀린 보기로 정답이 되겠습니다.

---

마치며...

이번 문제 풀이가 개인적으로 풀이를 포스팅하는데 제일 오래 걸린 문제 같습니다.

정말 이노무 노드들 그리느라 짜증나 죽는줄 알았습니다 T^T

그래도 풀이과정을 보시며 조금이나마 이해가 가는 공시생들이 있었으면 좋겠습니다.

화이팅!