输者树
完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_31loserTree
输者树：每一个内部节点所记录的都是比赛的输者，晋级的节点记录在边上。本文中，赢者是分数较低的那个，输者是分数高的那个。教材的举例是这样的。
更好理解的解释是，参考地址。
- a与b比赛，输者是b，赢者是a，将b放到内部节点，将a放到边上
- c与d比赛，输者是d，赢者是c，将d放到内部节点，将c放到边上
- e与f比赛，输者是e，赢者是f，将e放到内部节点，将f放到边上
- g与h比赛，输者是h，赢者是g，将h放到内部节点，将g放到边上
- a与c比赛，输者是c，赢者是a，将c放到内部节点，将a放到边上
- f与g比赛，输者是g，赢者是f，将g放到内部节点，将f放到边上
- a与f比赛，输者是a，赢者是f，将a放到内部节点，将f放到边上
- 将最终赢者放到数组的第0个元素
在loserTree的模板实现中，可以使用一个数组来存储输者、另一个数组存储赢者。
输者树比赢者树的优势
当改变的元素是上一场比赛的最终赢家的话，内部节点存储了所有该赢家的输者。在重新组织比赛时，只需要与父亲节点进行比较，而不需要获取到父亲节点的另外一个节点，然后与其比较，可以减少访存的时间。
输者树的实现
main.cpp
/*
Project name : _30winnerTree
Last modified Date: 2023年12月19日16点48分
Last Version: V1.0
Descriptions: 最小输者树——main函数
*/
#include "MinimumLoserTree.h"
int main(){
MinimumLoserTreeTest();
return 0;
}
MinimumLoserTree.h
/*
Project name : _30winnerTree
Last modified Date: 2023年12月19日16点48分
Last Version: V1.0
Descriptions: 最小输者树——模板类
*/
#ifndef _31LOSERTREE_MINIMUMLOSERTREE_H
#define _31LOSERTREE_MINIMUMLOSERTREE_H
#include<iostream>
#include "loserTree.h"
#include "myExceptions.h"
using namespace std;
void MinimumLoserTreeTest();
template<class T>
class MinimumLoserTree : public loserTree<T> {
public:
/*构造函数*/
explicit MinimumLoserTree(T *thePlayer = nullptr, int theNumberOfPlayers = 0) {
tree = nullptr;
advance = nullptr;
initialize(thePlayer, theNumberOfPlayers);
}
/*析构函数*/
~MinimumLoserTree() {
delete[] tree;
delete[] advance;
}
void initialize(T *thePlayer, int theNumberOfPlayers);//初始化
[[nodiscard]] int getTheWinner() const { return tree[0]; };//输出当前的赢者
void rePlay(int thePlayer, T newvalue);//重构
void output() const;
private:
int numberOfPlayers{};
int *tree;// 记录内部结点，tree[0]是最终的赢者下标，不使用二叉树结点，因为父子关系都是通过计算得出
int *advance;// 记录比赛晋级的成员
T *player;//参与比赛的元素
int lowExt{};//最底层外部结点的个数,2*(n-s)
int offset{};//2*s-1
void play(int, int, int);
int winner(int x, int y) { return player[x] <= player[y] ? x : y; };//返回更小的元素下标
int loser(int x, int y) { return player[x] <= player[y] ? y : x; };//返回更大的元素下标
};
template<class T>
void MinimumLoserTree<T>::initialize(T *thePlayer, int theNumberOfPlayers) {
int n = theNumberOfPlayers;
if (n < 2) {
throw illegalParameterValue("must have at least 2 players");
}
player = thePlayer;
numberOfPlayers = n;
// 删除原来初始化的内存空间，初始化新的内存空间
delete[] tree;
delete[] advance;
tree = new int[n + 1];
advance = new int[n + 1];
// 计算s
int s;
for (s = 1; 2 * s <= n - 1; s += s);//s=2^log(n-1)-1（常数优化速度更快），s是最底层最左端的内部结点
lowExt = 2 * (n - s);
offset = 2 * s - 1;
for (int i = 2; i <= lowExt; i += 2)//最下面一层开始比赛
play((i + offset) / 2, i - 1, i);//父结点计算公式第一条
int temp = 0;
if (n % 2 == 1) {//如果有奇数个结点，一定会存在特殊情况，需要内部节点和外部节点的比赛
play(n / 2, advance[n - 1], lowExt + 1);
temp = lowExt + 3;
} else temp = lowExt + 2;//偶数个结点，直接处理次下层
for (int i = temp; i <= n; i += 2)//经过这个循环，所有的外部结点都处理完毕
play((i - lowExt + n - 1) / 2, i - 1, i);
tree[0] = advance[1];//tree[0]是最终的赢者，也就是决赛的赢者
}
template<class T>
void MinimumLoserTree<T>::play(int p, int leftChild, int rightChild) {
// tree结点存储相对较大的值，也就是这场比赛的输者
tree[p] = loser(leftChild, rightChild);
// advance结点存储相对较小的值，也就是这场比赛的晋级者
advance[p] = winner(leftChild, rightChild);
// 如果p是右孩子
while (p % 2 == 1 && p > 1) {
tree[p / 2] = loser(advance[p - 1], advance[p]);
advance[p / 2] = winner(advance[p - 1], advance[p]);
p /= 2;//向上搜索
}
}
template<class T>
void MinimumLoserTree<T>::rePlay(int thePlayer, T newvalue) {
int n = numberOfPlayers;
if (thePlayer <= 0 || thePlayer > n) {
throw illegalParameterValue("Player index is illegal");
}
player[thePlayer] = newvalue;
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 = advance[2 * matchNode];
rightChild = thePlayer;
} else {
leftChild = 2 * matchNode - n + 1 + lowExt;//这个操作是因为上面matchNode计算中/2取整了
rightChild = leftChild + 1;
}
}
//到目前位置，我们已经确定了要比赛的场次以及比赛的选手
//下面进行比赛重构，也就是和赢者树最大的不同，分两种情况
if (thePlayer == tree[0]) {//当你要重构的点是上一场比赛的赢家的话，过程比赢者树要简化，简化之后只需要和父亲比较，不需要和兄弟比较
for (; matchNode >= 1; matchNode /= 2) {
int oldLoserNode = tree[matchNode];//上一场比赛的输者
tree[matchNode] = loser(oldLoserNode, thePlayer);
advance[matchNode] = winner(oldLoserNode, thePlayer);
thePlayer = advance[matchNode];
}
} else {//其他情况重构和赢者树相同
tree[matchNode] = loser(leftChild, rightChild);
advance[matchNode] = winner(leftChild, rightChild);
if (matchNode == n - 1 && n % 2 == 1) {//特殊情况
// 特殊在matchNode/2后，左孩子是内部节点，右孩子是外部节点
matchNode /= 2;
tree[matchNode] = loser(advance[n - 1], lowExt + 1);
advance[matchNode] = winner(advance[n - 1], lowExt + 1);
}
matchNode /= 2;
for (; matchNode >= 1; matchNode /= 2) {
tree[matchNode] = loser(advance[matchNode * 2], advance[matchNode * 2 + 1]);
advance[matchNode] = winner(advance[matchNode * 2], advance[matchNode * 2 + 1]);
}
}
tree[0] = advance[1];//最终胜者
}
template<class T>
void MinimumLoserTree<T>::output() const
{
cout << "number of players = " << numberOfPlayers
<< " lowExt = " << lowExt
<< " offset = " << offset << endl;
cout << "complete loser tree pointers are" << endl;
for (int i = 1; i < numberOfPlayers; i++)
cout << tree[i] << ' ';
cout << endl;
}
#endif //_31LOSERTREE_MINIMUMLOSERTREE_H
MinimumLoserTree.cpp
/*
Project name : _30winnerTree
Last modified Date: 2023年12月19日16点48分
Last Version: V1.0
Descriptions: 最小输者树——测试函数
*/
#include "MinimumLoserTree.h"
void MinimumLoserTreeTest(){
int n;
cout << "Enter number of players, >= 2" << endl;
cin >> n;
if (n < 2)
{cout << "Bad input" << endl;
exit(1);}
int *thePlayer = new int[n + 1];
cout << "Enter player values" << endl;
for (int i = 1; i <= n; i++)
{
cin >> thePlayer[i];
}
MinimumLoserTree<int> *w =
new MinimumLoserTree<int>(thePlayer, n);
cout << "The loser tree is" << endl;
w->output();
w->rePlay(2, 0);
cout << "Changed player 2 to zero, new tree is" << endl;
w->output();
w->rePlay(3, -1);
cout << "Changed player 3 to -1, new tree is" << endl;
w->output();
w->rePlay(7, 2);
cout << "Changed player 7 to 2, new tree is" << endl;
w->output();
delete [] thePlayer;
delete w;
}
loserTree.h
/*
Project name : _30winnerTree
Last modified Date: 2023年12月19日16点48分
Last Version: V1.0
Descriptions: 最小输者树——虚基类
*/
#ifndef _31LOSERTREE_LOSERTREE_H
#define _31LOSERTREE_LOSERTREE_H
template<class T>
class loserTree {
public:
virtual ~loserTree() {}
virtual void initialize(T *thePlayer, int number) = 0;
virtual int getTheWinner() const = 0;
virtual void rePlay(int thePLayer, T newvalue) = 0;
};
#endif //_31LOSERTREE_LOSERTREE_H
myExceptions.h
/*
Project name : _30winnerTree
Last modified Date: 2023年12月18日16点28分
Last Version: V1.0
Descriptions: 异常汇总
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>
#include <utility>
using namespace std;
// illegal parameter value
class illegalParameterValue : public std::exception
{
public:
explicit illegalParameterValue(string theMessage = "Illegal parameter value")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// illegal input data
class illegalInputData : public std::exception
{
public:
explicit illegalInputData(string theMessage = "Illegal data input")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// illegal index
class illegalIndex : public std::exception
{
public:
explicit illegalIndex(string theMessage = "Illegal index")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// matrix index out of bounds
class matrixIndexOutOfBounds : public std::exception
{
public:
explicit matrixIndexOutOfBounds
(string theMessage = "Matrix index out of bounds")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// matrix size mismatch
class matrixSizeMismatch : public std::exception
{
public:
explicit matrixSizeMismatch(string theMessage =
"The size of the two matrics doesn't match")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// stack is empty
class stackEmpty : public std::exception
{
public:
explicit stackEmpty(string theMessage =
"Invalid operation on empty stack")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// queue is empty
class queueEmpty : public std::exception
{
public:
explicit queueEmpty(string theMessage =
"Invalid operation on empty queue")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// hash table is full
class hashTableFull : public std::exception
{
public:
explicit hashTableFull(string theMessage =
"The hash table is full")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// edge weight undefined
class undefinedEdgeWeight : public std::exception
{
public:
explicit undefinedEdgeWeight(string theMessage =
"No edge weights defined")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// method undefined
class undefinedMethod : public std::exception
{
public:
explicit undefinedMethod(string theMessage =
"This method is undefined")
{message = std::move(theMessage);}
void outputMessage() {cout << message << endl;}
private:
string message;
};
#endif
运行结果
"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_31loserTree\cmake-build-debug\_31loserTree.exe"
Enter number of players, >= 2
8
Enter player values
4
6
5
9
8
2
3
7
The loser tree is
number of players = 8 lowExt = 8 offset = 7
complete winner tree pointers are
1 3 7 2 4 5 8
Changed player 2 to zero, new tree is
number of players = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 3 7 1 4 5 8
Changed player 3 to -1, new tree is
number of players = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 2 7 1 4 5 8
Changed player 7 to 2, new tree is
number of players = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 2 7 1 4 5 8
Process finished with exit code 0
