数据结构与算法——竞赛树

数据结构与算法——竞赛树

• 竞赛树分为赢者树和输者树，赢者树更直观，输者树实现更高效。
• 比赛用二叉树来描述，每个外部节点表示一名选手，每个内部节点表示一场比赛，同一层内部节点代表一轮比赛，可以同时进行。
  
  如果竞赛树是完全二叉树，则对于n个选手的比赛，最少的比赛场次为 l o g 2 n log_2n log2​n。
• 竞赛树不全是完全二叉树，但是完全二叉树可以是比赛的次数最少，竞赛树也成为选择树。

2.1 定义
（1）赢者树：有n个选手的赢者树是一个完全二叉树，有n个外部节点和n-1个内部节点，每个内部节点记录的是该节点比赛的赢者。
分类：最大赢者树、最小赢者树（平局的时候左孩子选手获胜）
优点：当一个选手分数改变时，修改竞赛树比较容易。
2.2 抽象数据类型winnerTree
假设：选手个数一定，初始化后不能增减选手。

选手本身并不是赢者树的组成部分，内部节点才是。

template<class T>
class winnerTree
{
public:virtual ~winnerTree() {}virtual void initialize(T* thePlayer, int theumberOfPlayers) = 0;// create winner tree with thePlayer[1:numberOfPlayers]virtual int winner() ct = 0;// return index of winnervirtual void rePlay(int thePLayer) = 0;// replay matches following a change in thePLayer
};

2. 赢者树的实现
（1）表示

n名选手，n-1个内部节点分别对应数组player[1: n]，tree[1: n-1]
对于任何一个外部节点player[i]，其父节点tree[p]由以下公式给出：
p = { ( i  o f f s e t ) / 2 i ≤ l o w E x t ( i − l o w E x t  n − 1 ) / 2 i > l o w E x t p=\left\{ \begin{aligned} (ioffset)/2 &&&&&& {i\leq lowExt } \\ (i-lowExtn-1)/2 &&&&&& {i >lowExt} \end{aligned} \right. p={(ioffset)/2(i−lowExtn−1)/2​​​​​​i≤lowExti>lowExt​
其中， s = 2 ∣ l o g 2 ( n − 1 ) ∣ s=2^{|log_2(n-1)|} s=2∣log2​(n−1)∣、 o f f s e t = 2 ∗ s − 1 offset=2*s-1 offset=2∗s−1
（2）初始化
从右孩子开始，逐层往上，且每层从左往右依次考察右孩子选手。
（）类completeWinnerTree

template<class T>
class completeWinnerTree : public winnerTree<T>
{
public:completeWinnerTree(T* thePlayer, int theumberOfPlayers){tree = ULL;initialize(thePlayer, theumberOfPlayers);}~completeWinnerTree() { delete[] tree; }void initialize(T*, int);int winner() ct{return tree[1];}int winner(int i) ct{return (i < numberOfPlayers) ? tree[i] : 0;}// return winner of match at node ivoid rePlay(int);void output() ct;
private:int lowExt;           // lowest-level external nodesint offset;           // 2^log(n-1) - 1int* tree;            // array for winner treeint numberOfPlayers;T* player;            // array of playersvoid play(int, int, int);
};

最先适配法求解箱子问题
相邻适配法求解箱子装载问题