[2019 5급 공무원 2차] 자료구조론 제 5문

2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 5문

 

제 5 문. 선택 트리(selection tree)는 완전 이진 트리(complete binary tree)를 사용하여 토너먼트 경기 방식을 통해 트리를 구축하는 자료구조로서 승자 트리(winner tree)와 패자 트리(loser tree)가 있다. 선택 트리를 사용하여 키 값이 가장 작은 원소를 선택한다고 할 때, 승자 트리에서는 형제 노드끼리 값을 비교하여 값이 작은 원소가 승자가 되어 부모 노드로 복사된 다음 토너먼트 경쟁을 계쏙하는 반면, 패자 트리에서는 키 값이 큰 패자는 부모 노드에 복사되고, 키 값이 작은 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경쟁을 계속 하는 형태로 트리를 구성한다. 따라서 승자 트리에서는 루트(1번 노드)에 결승 토너먼트의 승자가, 패자 트리에서는 루트(1번 노드)에 결승 토너먼트의 패자가 나타나며, 전체 승자는 루트 위에 별도로 위치한 0번 노드에 나타난다. 다음과 같이 오름차순으로 정렬된 8개의 런(run)이 있을 때, 물음에 답하시오. (단, 각 런의 첫 번째 원소를 완전 이진 트리의 단말(leaf) 노드로 복사한 다음 선택 트리의 구축이 시작된다.) (총20점)

런1 : 8,11
런2 : 13,14
런3 : 2,16,21
런4 : 5,17
런5 : 9,19,25
런6 : 4,15,22
런7 : 7,10
런8 : 1,12,20

 

 

 

선택 트리(Selection Tree)

 

선택 트리는 토너먼트 트리라고도 불리며

먼저 Run이라는 레코드에 정렬된 데이터가 존재한다.

이 레코드의 최상단, 가장 앞에 갚이 Leaf 노드가 되고

leaf 노드부터 부모의 자리를 차지하기 위해 경쟁하며

최종 우승 자리인 root까지 값을 채우는 트리이다.

 

 

 

1) 위의 런으로부터 만들어지는 승자 트리를 그리시오. (2점)

 

정답 )

 

승자트리는 자식 중 더 작은 값이 부모자리를 차지하는 트리이다.

 

 

 

 

2) 위의 런으로부터 만들어지는 패자 트리를 그리시오. (2점)

 

정답 )

 

패자트리는 각 라운드에서 패배한 노드의 값을 적어주면 된다.

승자트리로부터 각 레벨에서 패배한 노드값을 적는다.

 

 

 

 

 

 

3) 1)에서 만들어진 선택 트리로부터 가장 작은 원소 2개를 삭제한다고 할 때, 원소를 삭제할 대마다 변경되는 트리를 순서대로 그리시오.(3점)

 

정답)

 

Step 1.가장 작은 원소 1을 삭제(제거)

 

 

 

 

Step 2.승자 트리 재구성

 

 

 

 

Step 3. 가장 작은 원소 2를 삭제(제거)

 

 

 

 

Final. 승자트리 재구성

 

 

 

 

 

 

 

 

4) 2)에서 만들어진 선택 트리로부터 가장 작은 원소 2개를 삭제한다고 할 때, 원소를 삭제할 대마다 변경되는 트리를 순서대로 그리시오.(3점)

 

Step 1.최종 승자인 1을 삭제(제거)하면서 2가 그다음으로 작은 원소가 되며 새로운 패자트리를 재구성한다. 즉, 1)에서 구한 첫 번째 원소 삭제에 대한 승자트리의 패자트리이다. 재구성된 패자트리는 다음과 같다.

 

 

 

 

Final.새로운 최종 승자인 2를 삭제(제거)하면서 4가 그다음으로 작은 원소가 되며 새로운 패자트리를 재구성한다. 즉, 1)에서 구한 두 번째 원소 삭제에 대한 승자트리의 패자트리이다. 재구성된 패자트리는 다음과 같다.