/*
토너먼트 트리(Winner Tree A.K.A Tournament Tree)
*/
#include <iostream>
using namespace std;
struct player
{
int id, key; //id: 몇번째 플레이어, key: 값
operator int() const
{
return key;
}
};
template<class T>
class winnerTree
{
public:
virtual ~winnerTree() {}
virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;
// theNumberOfPlayers만큼의 노드를 가진 승자트리 생성
virtual int winner() const = 0;
// 승자노드의 인덱스 반환
virtual void rePlay(int thePLayer) = 0;
// 플레이어의 값을 바꾼다음 다시 승자트리를 돌리는 함수
};
template <typename T>
class completeWinnerTree : public winnerTree<T>
{
private:
int lowExt; // 제일 밑에 있는 말단 노드
int offset; // 토너먼트가 진행되는 노드들의 마지막 인덱스
int *tree; // 승자트리를 표현한 배열
int numberOfPlayers; //토너먼트에 참가한 노드 수
T *player; // 플레이어들을 저장한 배열
public:
completeWinnerTree(T *thePlayer, int theNumberOfPlayers)
{
tree = NULL;
initialize(thePlayer, theNumberOfPlayers); //승자트리 초기화
}
~completeWinnerTree()
{
delete[] tree;
}
void play(int p, int leftChild, int rightChild)
{// tree[p]부터 토너먼트 시작
//p의 왼쪽 자식, 오른쪽 자식->leftChild, rightChild
tree[p] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild;
// 오른쪽 자식이라면 더 진행할 수 있다
while (p % 2 == 1 && p > 1)
{ //오른쪽 자식이라면
tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ? tree[p - 1] : tree[p];
p /= 2; // 부모로 간다
}
}
void initialize(T *thePlayer, int theNumberOfPlayers)
{// 승자트리 생성
int n = theNumberOfPlayers;
if (n < 2)
{
cout << "플레어의 수는 2 이상이어야 합니다" << endl;
return;
}
player = thePlayer;
numberOfPlayers = n;
delete[] tree;
tree = new int[n];
//s = 2^log (n-1) 계산
int i, s;
for (s = 1; 2 * s <= n - 1; s += s);
lowExt = 2 * (n - s);
offset = 2 * s - 1;
// 말단노드까지 토너먼트 진행
for (i = 2; i <= lowExt; i += 2)
play((offset + i) / 2, i - 1, i);
// 아직 토너먼트에 참가하지 않은 말단노드가 있다면 추가적인 토너먼트 진행
if (n % 2 == 1)
{// n이 홀수인 경우
play(n / 2, tree[n - 1], lowExt + 1);
i = lowExt + 3;
}
else //짝수인 경우
i = lowExt + 2;
// i는 남은 말단 노드 중 제일 왼쪽에 있는 노드 인덱스
for (; i <= n; i += 2)
play((i - lowExt + n - 1) / 2, i - 1, i);
}
int winner() const
{
return tree[1];
}
//i 인덱스의 승자를 반환
int winner(int i) const
{
return (i < numberOfPlayers) ? tree[i] : 0;
}
void rePlay(int thePlayer)
{// thePlayer의 값이 변동되었을 경우 재경기
int n = numberOfPlayers;
if (thePlayer <= 0 || thePlayer > n)
{
cout << "플레이어의 수가 이상합니다" << endl;
return;
}
int matchNode, // 다음 경기가 이루어질 노드
leftChild, // 그 노드의 왼쪽 자식
rightChild; // 그 노드의 오른쪽 자식
// 첫번째 경기가 이루어질 노드를 찾고 그 자식까지 찾는다
if (thePlayer <= lowExt)
{// 제일 밑에 층에서부터 시작
matchNode = (offset + thePlayer) / 2;
leftChild = 2 * matchNode - offset;
rightChild = leftChild + 1;
}
else
{
matchNode = (thePlayer - lowExt + n - 1) / 2;
if (2 * matchNode == n - 1)
{
leftChild = tree[2 * matchNode];
rightChild = thePlayer;
}
else
{
leftChild = 2 * matchNode - n + 1 + lowExt;
rightChild = leftChild + 1;
}
}
tree[matchNode] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild;
// n이 홀수인 경우(특별한 케이스)
if (matchNode == n - 1 && n % 2 == 1)
{
matchNode /= 2; // 부모로 이동
tree[matchNode] = (player[tree[n - 1]] <= player[lowExt + 1]) ? tree[n - 1] : lowExt + 1;
}
// 남은 경기 진행
matchNode /= 2; // 부모로 이동
for (; matchNode >= 1; matchNode /= 2)
tree[matchNode] = (player[tree[2 * matchNode]] <= player[tree[2 * matchNode + 1]]) ? tree[2 * matchNode] : tree[2 * matchNode + 1];
}
void output() const //출력
{
int count = 1;
cout << "노드의 수 = " << numberOfPlayers << endl;
cout << "승자트리 출력" << endl;
for (int i = 1; i < numberOfPlayers; i++)
{
int space = 1;
for (int j = 1; j <= count; j++)
space += space;
cout << tree[i] << ' ';
if (i == (space - 1))
{
cout << endl;
count++;
}
}
cout << endl;
}
};
int main(void)
{
int n;
cout << "노드 수 입력, 단 2개 이상이여야한다: ";
cin >> n;
if (n < 2)
{
cout << "잘못된 입력" << endl;
exit(1);
}
player *thePlayer = new player[n + 1]; //0번째 인덱스 사용하지 않기 때문에
cout << "노드의 값 입력" << endl;
for (int i = 1; i <= n; i++)
{
cin >> thePlayer[i].key;
thePlayer[i].id = i;
}
completeWinnerTree<player> *w = new completeWinnerTree<player>(thePlayer, n);
cout << "승자트리는!" << endl;
w->output();
thePlayer[2].key = 0;
w->rePlay(2);
cout << "2번째 플레이어의 값을 0으로 변경" << endl;
w->output();
thePlayer[3].key = -1;
w->rePlay(3);
cout << "3번째 플레이어의 값을 -1로 변경" << endl;
w->output();
thePlayer[7].key = 2;
w->rePlay(7);
cout << "7번째 플레이어의 값을 2로 변경" << endl;
w->output();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://bitbucket.org/vermapratyush/online-judges/src/2b22910da6fa3a07e820fb244c700b6e16c9e9f5/codes-sahni/completeWinnerTree.h?at=master&fileviewer=file-view-default
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*https://bitbucket.org/vermapratyush/online-judges/src/2b22910da6fa3a07e820fb244c700b6e16c9e9f5/codes-sahni/completeWinnerTree.h?at=master&fileviewer=file-view-default 에 있는 코드를 조금 수정하고 나름대로 주석을 달았습니다.
*책에서도 별다른 예제코드가 없었기 때문에 위 링크에 있는 코드를 거의 그대로 가져왔습니다.(승자트리를 작성할 때는 배열을 사용하는 것이 효율적인 것을 알게되었습니다)