6 min to read

자료구조(13) - 승자 트리와 패자 트리

승자 트리의 ADT 작성 및 구현

Featured image

🔚 짧게 하는 복습

✅ 1. 힙의 ADT를 구현할 수 있다.

✅ 2. 우선순위 큐가 무엇인지 이해한다.

혹시 기억이 안 난다면, 다시 돌아가자

이번 시간은 드디어 우리 자료구조 트리 강의의 마지막이다.

본론으로 들어가기 전에, 혹시 스포츠에서 트리 자료구조를 본 적이 있는가?

아마 없다고 하겠지만, 사실 우리에게 굉장히 익숙한 완전 이진 트리(FBT)가 있다.

바로 토너먼트 대진표이다.

32강, 16강, 8강, 4강, 결승 등의 단계에서 이진 트리를 이용해 나타내는 것을 많이 봐왔다.

우리는 이런 것처럼, 참가자들의 결괏값을 입력받아서 대결 결과를 계산하는 특별한 자료구조를 배워볼 것이다.

승자 트리란?

우리가 익숙한 토너먼트 대진표처럼, 승자 트리(Winner)는 자식 노드들의 값 중 더 우수한 결과를 부모 노드에 가진 트리를 말한다.

즉, 루트 노드는 참가자 중 가장 우수한 결과를 가지며 루트 노드의 값을 가진 참가자를 우승자(Winner)라고 한다.

패자 트리는 그 반대로, 자식 노드들의 값 중 더 좋지 못한 결과를 부모 노드에 가진 트리를 말한다. 또 루트 노드에 있는 값을 가진 참가자가 패자(Loser)가 된다.

승자 트리는 FBT이기에, 배열 및 연결리스트로도 구현할 수 있다.

편의를 위해 배열로 구현하고, 연결리스트는 과제로 남기겠다.

승자트리 ADT

  • 자료 : 정수
  • 기능1 삽입 : 참가자들을 승자 트리에 모두 입력한다.
  • 기능2 조회 : 승자를 알려준다.
  • 기능3 갱신 : 특정 참가자의 결과를 변경하고, 승자 트리를 갱신한다.

    • 역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정할 수 있다.

    승자 트리의 구현

    보통 정적 배열을 이용하는 승자 트리의 특성상 입력과 조회는 굉장히 간단하고, 갱신은 Heapify와 유사하다.

    직접 코드를 짜보자.

    #include <stdio.h>
#define MAX 1000 // 여분의 배열 공간
#define p_num 8 // 참가자 수

int nodes = p_num * 2 -1;// 필요한 배열 원소의 수(FBT의 성질)

/*
자료 : 정수
기능1 삽입 : 참가자들을 승자 트리에 모두 입력한다.
기능2 조회 : 승자를 알려준다.
기능3 갱신 : 특정 참가자의 결과를 변경하고, 승자 트리를 갱신한다.
*/

int parent(const int index) {
	return (index -1)/ 2;
}

//+) 핵심 기능 make_winner_tree - 위너 트리 구조로 만듦
int make_winner_tree(int winner_tree[], int level_nodes) {
	if (level_nodes == 1) {
		return 1;
		// 탈출 조건 및 1 반환
	}

	int p_begin_index = level_nodes -1;

	for (int i = 0; i < p_begin_index; i += 2) {
		int left = winner_tree[p_begin_index + i];
		int right = winner_tree[p_begin_index + i + 1];
		int winner = (left < right) ? left : right;
		// 작을수록 승자

		winner_tree[parent(p_begin_index + i)] = winner;
	}

	return make_winner_tree(winner_tree, level_nodes / 2);
}

//기능1 삽입
int insert(int winner_tree[], int participants[]) {
	int p_begin_index = p_num -1;
	// FBT의 성질 이용(8강이면 참가자 정보는 8~ 15에 저장)
	// 그리고 참가자의 수이기도 함.

	for (int i = 0; i <= p_begin_index; i++) {
		winner_tree[p_begin_index + i] = participants[i];
	}

	for (int i = p_num-1; i < nodes; i++) {
		printf("%d ", winner_tree[i]);
	}// 참가자 출력

	printf("\n\n");

	make_winner_tree(winner_tree, p_num);
	// 승자 트리로 만듦
	return 0;
}

//기능2 조회
int search(int winner_tree[]) {
	printf("The winner is %d\n\n", winner_tree[0]);
	return winner_tree[0];
	// 우승자 반환
}

//기능3 갱신
int update(int winner_tree[], const int index, const int value) {
// 특정 인덱스의 특정 값을 받아 반환
	int p_begin_index = p_num - 1;
	// FBT의 성질 이용(8강이면 참가자 정보는 7~ 15에 저장)
	// 그리고 참가자의 수이기도 함.

	if (index >= nodes || index < 0) {
		printf("There is no %d participant\n\n", index);
		return -1;
	}

	winner_tree[p_begin_index + index] = value;

	printf("The participant %d's result is changed with %d\n\n", index, value);

	make_winner_tree(winner_tree, p_num);
	// 승자 트리로 만듦

	return 0;
}


int main(void) {
	int winner_tree[MAX] = { 0, }; //
	int participants[p_num] = { 1, 5, 3, 4, 6, 9, 2, 7 };

	insert(winner_tree, participants);

	search(winner_tree);

	update(winner_tree, 0, 12);

	search(winner_tree);
}

    결과창

    1 5 3 4 6 9 2 7

The winner is 1

The participant 0's result is changed with 12

The winner is 2

    📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

    ✅ 1. 승자 트리의 ADT를 구현할 수 있다.

    ⚠️ 맨 마지막 리프 노드를 n개 가지는 FBT의 전체 노드는 2*n -1개이다.

    💣 과제,

    1. 연결리스트로 패자 트리를 구현해보자(난이도 하)