제5장 트리 - winner tree(승자트리)

소개

4. 승자트리를 구현하라. k>= 2개 런의 K원 합병을 수행하는 알고리즘을 작성하라.
k 개의 런에 총 n 개의 레코드가 있다면 수행시간이 임을 보여라.

1) 거의 line by line으로 주석이 달려있습니다.
2) 교재 중반부의 external sorting에서도 사용됩니다.

목차

vc++ 6.0

본문내용

/************************************************************************
winner_tree.c
*************************************************************************
* run 의 내부는 정렬이 된상태.
* tree : selection tree
* PNODE run[] : 런들에 대한 포인터
* nRec : 런내부 Record의 개수.
* MAX_RUN : 런의 개수. (항상 2의 n제곱승이 여야 한다.)
* key 는 절대로 `INT_MAX(2,147,483,647)`가 될 수 없다.
*************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <limits.h>

#define MAX_RUN 8
#define MAX_RECORD 8

// RUN의 노드.
typedef struct _NODE* PNODE ;
typedef struct _NODE
{
int key;
// other fields
} NODE;

// Selection Tree의 노드.
typedef struct _S_NODE* PSNODE;
typedef struct _S_NODE
{
int key; // key
short run_number; // 해당 키가 속하는 run의 번호.
short index; // 해당 키가 속하는 run의 record index
// other fields
} SNODE;

/*포인터 연산시 ( MAX_RECORD*NODE사이즈) 크기 만큼 메모리가 더해진다.*/
void selection_tree( NODE (*run)[MAX_RECORD] , int nRec , int nRun );

참고자료

· 없음