10-1. 선택트리

주요 용어

합병 정렬 : 차례로 정렬된 데이터 리스트를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정

선택 트리 : 합병 정렬에 사용하는 특수한 트리

승자 트리 : 각 노드가 두 개의 자식노드 보다 더 작은 값(승자)을 갖는 완전 이진트리

패자 트리 : 각 노드가 두 개의 자식노드 보다 더 큰 값(패자)을 가지며 최종 승자는 0번 노드에 저장하는 트리

숲 : 분리된 트리 모임, n (≧ 0) 개 이상의 분리된 트리 집합

 

 

 

01. 선택 트리

합병 정렬 : 차례로 정렬된 k개의 데이터 리스트를 완전한 순서를 유지하는 하나의 데이터 리스트로 만드는 과정

- 일반적으로 데이터 리스트가 k개인 경우 k-1번 비교를 통해 데이터 리스트에서 가장 작은 값이나 가장 큰 값을 결정함

- 선택 트리를 이용하여 비교 횟수를 줄일 수 있음

 

승자 트리

- 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진트리

- 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사

- 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함

- 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨

 

 

첫 번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두 번째 비교 횟수가 감소됨

- 재구성 과정에서 빈 리스트가 생기면 큰 값(∞)을 넣어줌

 

패자 트리

: 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진트리라는 점은 승자 트리와 같지만, 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐

 

- 최상위 0번 노드에는 최종 승자를 저장함

- 트리의 각 내부 노드에는 승자가 아닌 패자를 저장 (즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)

- 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장

패자 트리

: 0번 노드에 최솟값이 있으므로 이 값을 제거하여 전체 리스트에 저장함

- 제거된 값을 가지고 있던 4번 리스트 head에 위치한 값 24를 패자 트리에 올려 보내고 경쟁을 시킴

- 패자 트리를 재구성함