선택 트리(selection tree)
하나의 순서 순차(ordered sequence)로 합병 될 런(run)이라 부르는 k개의 순서 순차가 있다고 가정하자.
각 런은 key라고 하는 지정된 필드에 따라 비감소 순서로 정렬된 약간의 레코드들로 구성된다.
선택 트리(selection tree) 자료 구조를 이용하면, 다음으로 가장 작은 레코드를 발겨하는데 필요한 비교 횟수를 줄일 수 있다.
선택 트리에는 승자 트리(winner tree)와 패자 트리(loser tree) 두 종류가 있다.
승자 트리(winner tree)
승자 트리는 각 노드가 2개의 자식 노드 중 더 작은 노드를 나타내는 완전 이진 트리이다.
그러므로 루트 노드는 트리에서 가장 작은 노드를 나타낸다.
각 리프들은 각 런에 첫번째 값이다.
승자 트리는 일종의 작은것이 올라가는 토너먼트 이다.
승자 트리의 과정은
a) 승자 트리는 런을 합병하고
b) 이를 재구성하는 작업이다.
패자 트리(loser tree)
각 비리프 노드가 패자에 대한 포인터를 유지하는 선택 트리를 패자 트리(loser tree)라고 한다.
승자 트리에서는 자매와 비교하지만,
패자 트리에서는 부모와 비교한다.
승자 트리에서 떨어진 녀석을 올려주면 된다.
실습 예제
다음을 만족하는 Winner Tree 프로그램을 구현하라
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
K D 1,1 D 1,2 … -1
D 2,1 D 2,2 … -1
…
D K,1 D K,2 … -1
K: run의 갯수, Di, j : i번째 run의 j번째 key, -1은 각 run의 끝을 나타낸다. K ≤ 32이
며, key는 모두 양수이고 각 run들의 key갯수는 100개를 넘지 않는다고 가정한다.
2) 각 run들의 첫번째 key 대해서 Winner Tree를 Array Representation으로 구성한다.
Winner는 둘 중의 작은 값으로 정의한다.
3) 구성된 Winner Tree의 최종 Winner를 출력한다.
4) Winner Tree를 Level Order와 Inorder Traversal한 결과를 각각 출력한다.
5) Winner가 나온 run의 다음 key를 이용해서 Winner Tree를 Restructuring한 후 3)
과 4)를 수행한다.
입력 값
input.txt
8
10 15 16 -1
9 20 38 -1
20 20 30 -1
6 15 25 28 -1
8 15 50 -1
9 11 16 -1
90 95 99 -1
17 18 20 -1
코드
/*
Description : 선택 트리의 Winner tree를 구현하기. 그리고 빠진 자리에 Restructuring 하여 다시 Winner Tree 수행
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_BUFFER 8
int TEMP[MAX_BUFFER][MAX_BUFFER];
int stack[MAX_BUFFER];
int run = 0;
int cnt = 0;
typedef struct R_NODE* RUN_NODE;
typedef struct R_NODE //RUN의 노드
{
int key; //다른 필드
}R_NODE;
typedef struct S_NODE* SELECT_NODE; //WiNNER의 노드
typedef struct S_NODE
{
int key;
short run_number; //해당 키가 속하는 run의 번호.
short index; //해당 키가 속하는 run의 record index
}S_NODE;
void Winner_tree(R_NODE **RUN, int nRUN);
void open();
void print(int n);
void iterinorder();
void Restructuring(R_NODE **RUN, int nRUN);
SELECT_NODE selcTree;
int main()
{
open();
R_NODE **RUN; //RUN 2차원 배열
RUN = (R_NODE**)malloc(sizeof(R_NODE*) * MAX_BUFFER);
for (int i = 0; i < MAX_BUFFER; i++)
RUN[i] = (R_NODE*)malloc(sizeof(R_NODE*) * MAX_BUFFER);
for (int i = 0; i < run; i++)
for (int j = 0; j < cnt; j++)
RUN[i][j].key = TEMP[i][j];
Winner_tree(RUN, cnt);
printf("Level Order : ");
print(run);
printf("\nInorder : ");
iterinorder();
printf("\n");
Restructuring(RUN, cnt); //빠진 자리 채워넣기
printf("Level Order : ");
print(run);
printf("\nInorder : ");
iterinorder();
printf("\n");
free(RUN); //메모리 해제
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d", &run);
int i = 0, j = 0;
int item;
while (fscanf(fp, "%d", &item) != EOF)
{
TEMP[i][j] = item;
j++;
if (item == -1)
{
i++;
if (cnt < j) cnt = j;
j = 0;
}
}
}
void Winner_tree(R_NODE **RUN, int nRun)
{
// selection tree pointer
int i, j;
int compare; // 그 level의 비교 횟수
selcTree = (SELECT_NODE)malloc(sizeof(S_NODE)*run * 2);
for (i = 0; i<run; i++) //배열 초기화 작업
{
selcTree[i + run].index = 0;
selcTree[i + run].run_number = i;
selcTree[i + run].key = RUN[i][selcTree[i + run].index].key;
}
i = run;
compare = run / 2;
while (i>1)
{
for (j = 0; j<compare; j++)
{
selcTree[i / 2] = ((selcTree[i].key<selcTree[i + 1].key) ? selcTree[i] : selcTree[i + 1]);
i += 2; // 작은것(승자)이 부모로
}
i = compare;
compare /= 2;
}
printf("Winner : %3d \n", selcTree[1].key);
}
void iterinorder()
{
int i = 1;
int top = -1;
while (1) {
while (run * 2 > i) {
top++;
stack[top] = i;
i = i * 2;
}
if (top == -1)
return;
i = stack[top];
top--;
printf("%3d ", selcTree[i].key);
i = i * 2 + 1;
}
}
void print(int n)
{
int i;
for (i = 1; i < n * 2; i++)
printf("%3d ", selcTree[i].key);
}
void Restructuring(R_NODE **RUN, int nRun)
{
int i, j;
int compare; // 그 level의 비교 횟수
SELECT_NODE winner;
i = run;
compare = run / 2;
winner = selcTree + 1;
if (winner->index<run - 1)
{
// key 값 복사
selcTree[run + winner->run_number].key =
RUN[winner->run_number][(winner->index) + 1].key;
++(selcTree[run + winner->run_number].index); // 승자가 속한 런내의 인덱스포인터 증가
}
else //런내의 레코드가 남아 있지 않을 경우
{
// 최댓값으로 리셋
selcTree[run + winner->run_number].key = INT_MAX;
--nRun;
}
while (i>1)
{
for (j = 0; j<compare; j++)
{
selcTree[i / 2] = ((selcTree[i].key<selcTree[i + 1].key) ? selcTree[i] : selcTree[i + 1]);
i += 2;
}
i = compare;
compare /= 2;
}
printf("Winner : %3d \n", selcTree[1].key);
}
출력 값
