《数据结构、算法与应用 —— C++语言描述》学习笔记 — 竞赛树
一、赢者树二、二叉树的数组描述（补充）1、声明2、实现 三、赢者树1、抽象数据类型2、赢者树的表示3、声明4、初始化5、重新组织比赛6、获取胜者一、赢者树
假定有n个选手参加一次网球比赛。比赛规则是“突然死亡法”：一名选手只要输掉一场球，就被淘汰。一对一对选手进行比赛，最终只剩下一个选手保持不败。我们使用二叉树来描述这个比赛过程。每个外部节点表示一名选手，每个内部节点表示一场比赛，该内部节点的孩子表示比赛的选手。同一层的内部节点代表一轮比赛，可以同时进行：
如图，第一轮比赛，b和c的胜者为b，d和e的胜者为d；第二轮比赛，a和b的胜者为b，d和f的胜者为d；
最后一轮比赛，b和d的胜者为b。
事实上，如果我们使用完全二叉树实现，可以使比赛的场次达到最小（ ⌈ log 2 n ⌉ \lceil \log_2n \rceil ⌈log2n⌉）：
前面所列出的竞赛树称为赢者树，因为每一个内部节点所记录的都是比赛的赢者。除此之外，还有一种输者树，每一个内部节点所记录的都是比赛的输者。竞赛树也称为选择树。
赢者树的定义如下（为了便于实现，我们限制赢者树为完全二叉树）：
有n个选手的一棵赢者树是一棵完全二叉树，它有n个外部节点和n-1个内部节点，每个内部节点记录的是在该节点比赛的赢者。
为了确定一场比赛的赢者树，我们假设每个选手都有一个分数，而且有一个规则用来比较两个选手的分数以确定赢者。在最小赢者树中，分数大的选手获胜。在分数相等，即平局的时候，左孩子表示的选手获胜。
赢者树的一个优点在于，当一名选手的分数改变时，修改竞赛树比较容易。例如，当选手d的分数由9改为1时，只有从d到根的路径上的节点所标示的比赛可能需要重赛，而其他比赛的结果不受影响。有时，甚至连这种路径上的一些比赛也不需要重赛。当被改变的结果不影响某个内部节点的比赛结果时，该节点的所有祖先节点都不受影响。
在一棵n个选手的赢者树中，当一个选手的分数发生变化时，需要修改的比赛场次介于 1 ~ ⌈ log 2 n ⌉ \lceil \log_2n \rceil ⌈log2n⌉ 之间，因此，赢者树的重构需要耗时 ⌈ log 2 n ⌉ \lceil \log_2n \rceil ⌈log2n⌉。此外，n个选手的赢者树可以在 O ( n ) O(n) O(n)时间内初始化，方法是沿着从叶子到根的方向，在内部节点进行 n − 1 n-1 n−1 场比赛。
二、二叉树的数组描述（补充）
为了实现赢者树，显然我们不能前面实现的链式二叉树不能满足要求。因为对于赢者树来说，内部节点和外部节点的数据类型并不一致。因此，我们选择使用数组实现赢者二叉树。为此，我们首先需要先用实现二叉树的数组描述。
1、声明
#pragma once#include "binaryTree.h"#include <deque>#include <algorithm>template<typename T>class ArrayBinaryTree : public binaryTree<T>{public:ArrayBinaryTree();virtual ~ArrayBinaryTree();ArrayBinaryTree(const ArrayBinaryTree& other);ArrayBinaryTree(ArrayBinaryTree&& other);ArrayBinaryTree& operator=(const ArrayBinaryTree& other);ArrayBinaryTree& operator=(ArrayBinaryTree&& other);virtual bool empty() const override;virtual int size() const override;virtual void preOrder(std::function<void(T)> visitFunc) override;virtual void inOrder(std::function<void(T)> visitFunc) override;virtual void postOrder(std::function<void(T)> visitFunc) override;virtual void levelOrder(std::function<void(T)> visitFunc) override;int height();void makeTree(T* elements, int treeSize);protected:T* elements = nullptr;int treeSize = 0;std::function<void(T)> visitFunc;void makeCopyAndSwap(const ArrayBinaryTree& other);ArrayBinaryTree makeCopy(const ArrayBinaryTree& other);void swap(ArrayBinaryTree& other);void clear();void preOrder(int index);void inOrder(int index);void postOrder(int index);void levelOrder(int index);int height(int index);};
2、实现
大部分逻辑和链式二叉树类似，以中序遍历为例（注意树中的数据对应的数组元素从1开始）：
template<typename T>inline void ArrayBinaryTree<T>::inOrder(std::function<void(T)> visitFunc){this->visitFunc.swap(visitFunc);inOrder(1);}template<typename T>inline void ArrayBinaryTree<T>::inOrder(int index){if (index >= treeSize + 1){return;}inOrder(index * 2);visitFunc(elements[index]);inOrder(index * 2 + 1);}
三、赢者树
1、抽象数据类型
#pragma once#include <memory>template<typename T>class AbstractWinnerTree{public:virtual ~AbstractWinnerTree() {}virtual void initialize(T* player, int playerNum) = 0;virtual int winner() const = 0;virtual void replay(int playerIndex, T newValue) = 0;};
2、赢者树的表示
假设用完全二叉树的数组表示来表示赢者树。一棵赢者树有n名选手（player[1:n]），需要n-1个内部节点（tree[1:n-1]）。
这里的关键点在于找到外部节点与相关联的内部节点的映射关系。首先，我们可以把外部节点分成两部分，底层外部节点（即1-6）和上层外部节点（即7）。
对于底层外部节点，我们不难看出其编号与父节点编号呈线性关系，偏移量取决于最下层内部节点的开始编号（即4）。那么这个开始编号是怎么算出来的呢？根据内部节点个数n-1，我们可以得到树的高度为 h = ⌊ l o g 2 n − 1 ⌋ + 1 h=\lfloor log_2{n-1} \rfloor +1 h=⌊log2n−1⌋+1。那么开始编号应该为 s = 2 h − 1 s = 2^{h-1} s=2h−1，底部外部节点对应的父节点编号为： i − 1 2 + s \frac{i-1}{2}+s 2i−1+s。除此之外，我们可以得到下层外部节点的总数为 ( n − 1 − s + 1 ) ∗ 2 = ( n − s ) ∗ 2 (n-1-s+1)*2=(n-s)*2 (n−1−s+1)∗2=(n−s)∗2
对于上层节点，其编号取决于树的节点数。确切地来说，上层节点相当于将二叉树补充为满二叉树。那么我们可以计算每个上层内部节点的编号与其转化为内部节点应该有的编号的对应关系。也就是说，如果我们将编号为7的外部节点转化为内部节点，其编号为7（一样是巧合）。二者之间实际是存在一个偏移量的。以补充的第n个内部节点为例，其外部节点编号为 ( n − s ) ∗ 2 + 1 (n-s)*2+1 (n−s)∗2+1。因此，二者的偏移量为 n − 2 ∗ s + 1 n-2*s+1 n−2∗s+1。因此，上层节点对应的外部节点为 p − n + 2 ∗ s − 1 p-n+2*s-1 p−n+2∗s−1。我们可以进而得到上层节点对应的父节点。
综上，我们得出内部节点和外部节点的转化关系为：
p l a y e r = { i − 1 2 + s i ≤ ( n − s ) ∗ 2 p − n + 2 ∗ s − 1 2 i > ( n − s ) ∗ 2 player=\left\{ \begin{array}{rcl} \frac{i-1}{2}+s& {i \leq (n-s)*2}\\ \frac{p-n+2*s-1}{2}& {i > (n-s)*2}\\ \end{array} \right. player={2i−1+s2p−n+2∗s−1i≤(n−s)∗2i>(n−s)∗2
3、声明
为了简单起见，我们这里不实现拷贝赋值等功能。
#pragma once#include "AbstractWinnerTree.h"#include "../binaryTree/ArrayBinaryTree.h"#include <cmath>template<typename T>class WinnerTree : public AbstractWinnerTree<T>, public ArrayBinaryTree<int>{public:WinnerTree();WinnerTree(const WinnerTree& other) = delete;WinnerTree& operator=(const WinnerTree& other) = delete;~WinnerTree();void initialize(T* player, int playerNum) override;int winner() const override;void replay(int playerIndex, T newValue) override;private:T* player = nullptr;int playerNum = 0;int startIndexOfBottomInternalNodes = 0;int bottomExternalNodesNum = 0;void initExternalNodes(T* player, int playerNum);void initInternalNodes();void initInternalNodesWithExternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum);int initBottomInternalNodes(std::unique_ptr<int[]>& internalNodes);int initBorderInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum, int currentExternalIndex);void initUpperInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum, int currentExternalIndex);void initPureInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum);int replayBottomInternalNode(int playerIndex);int replayUpperInternalNode(int playerIndex, int parentNode);int replayBorderInternalNode(int playerIndex, int parentNode);void replayPureInternalNode(int parentNode);void comparePlayersAndSetInternal(int leftPlayer, int rightPlayer, int* internalNodes, int internalNodeIndex);};
4、初始化
构造的过程比较复杂。首先，我们要对外部节点进行一次拷贝（initExternalNodes），因为我们支持修改外部节点数值以重新比赛。然后我们才可以初始化内部节点（initInternalNodes）。内部节点的初始化同样分为两部分：初始化有外部节点为叶子的内部节点（initInternalNodesWithExternalNodes）以及纯内部节点（initPureInternalNodes）。初始化外部节点需要根据不同的内部节点进行分类初始化。首先是底层外部节点（initBottomInternalNodes）；然后是边界外部节点（initBottomInternalNodes），注意边界外部节点指其兄弟节点为内部节点的外部节点；最后是上层外部节点（initUpperInternalNodes）。这三种的编号映射关系计算各不相同。初始化纯内部节点的方式和前面初始化堆的方式类似。
template<typename T>inline void WinnerTree<T>::initialize(T* player, int playerNum){initExternalNodes(player, playerNum);initInternalNodes();}template<typename T>inline void WinnerTree<T>::initExternalNodes(T* player, int playerNum){this->playerNum = playerNum;this->player = new T[playerNum + 1];std::copy(player, player + playerNum + 1, this->player);}template<typename T>inline void WinnerTree<T>::initInternalNodes(){int internalNodesNum = playerNum - 1;std::unique_ptr<int[]> internalNodes(new int[internalNodesNum + 1]);startIndexOfBottomInternalNodes = std::pow(2, std::floor(std::log2(internalNodesNum)));bottomExternalNodesNum = (playerNum - startIndexOfBottomInternalNodes) * 2;initInternalNodesWithExternalNodes(internalNodes, internalNodesNum);initPureInternalNodes(internalNodes, internalNodesNum);this->makeTree(internalNodes.get(), internalNodesNum);}template<typename T>inline void WinnerTree<T>::initInternalNodesWithExternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum){int currentExternalIndex = initBottomInternalNodes(internalNodes);currentExternalIndex = initBorderInternalNodes(internalNodes, internalNodesNum, currentExternalIndex);initUpperInternalNodes(internalNodes, internalNodesNum, currentExternalIndex);}template<typename T>inline int WinnerTree<T>::initBottomInternalNodes(std::unique_ptr<int[]>& internalNodes){int currentExternalIndex = 1;for (; currentExternalIndex < bottomExternalNodesNum + 1; currentExternalIndex += 2){// 实际实现时，由于c++中取整默认向0取整，因此可以考虑将s值放到分子上int internalIndex = (currentExternalIndex + 2 * startIndexOfBottomInternalNodes - 1) / 2;comparePlayersAndSetInternal(currentExternalIndex, currentExternalIndex + 1, internalNodes.get(), internalIndex);}return currentExternalIndex;}template<typename T>inline int WinnerTree<T>::initBorderInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum, int currentExternalIndex){if ((playerNum - currentExternalIndex) % 2 == 0){int index = internalNodes[internalNodesNum];comparePlayersAndSetInternal(index, currentExternalIndex, internalNodes.get(), internalNodesNum / 2);currentExternalIndex++;}return currentExternalIndex;}template<typename T>inline void WinnerTree<T>::initUpperInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum, int currentExternalIndex){for (; currentExternalIndex < playerNum + 1; currentExternalIndex += 2){int internalIndex = (currentExternalIndex - playerNum - 1 + 2 * startIndexOfBottomInternalNodes) / 2;comparePlayersAndSetInternal(currentExternalIndex, currentExternalIndex + 1, internalNodes.get(), internalIndex);}}template<typename T>inline void WinnerTree<T>::initPureInternalNodes(std::unique_ptr<int[]>& internalNodes, int internalNodesNum){for (int index = (internalNodesNum - 1) / 2; index > 0; --index){auto leftIndex = internalNodes[index * 2];auto rightIndex = internalNodes[index * 2 + 1];this->player[leftIndex] > this->player[rightIndex] ? internalNodes[index] = leftIndex : internalNodes[index] = rightIndex;}}template<typename T>inline void WinnerTree<T>::comparePlayersAndSetInternal(int leftPlayer, int rightPlayer, int* internalNodes, int internalNodeIndex){if (this->player[leftPlayer] > this->player[rightPlayer]){internalNodes[internalNodeIndex] = leftPlayer;}else{internalNodes[internalNodeIndex] = rightPlayer;}}
5、重新组织比赛
重新组织比赛的计算方式我们前面已经学习过。需要注意，重新组织比赛也需要分三种情况分析，和上面类似。
template<typename T>inline void WinnerTree<T>::replay(int playerIndex, T newValue){this->player[playerIndex] = newValue;int parentNode = replayBottomInternalNode(playerIndex);parentNode = replayUpperInternalNode(playerIndex, parentNode);parentNode = replayBorderInternalNode(playerIndex, parentNode);replayPureInternalNode(parentNode);}template<typename T>inline int WinnerTree<T>::replayBottomInternalNode(int playerIndex){if (playerIndex < bottomExternalNodesNum + 1){int parentNode = (playerIndex + 2 * startIndexOfBottomInternalNodes - 1) / 2;int leftPlayer = (parentNode - startIndexOfBottomInternalNodes + 1) * 2 - 1;int rightPlayer = leftPlayer + 1;comparePlayersAndSetInternal(leftPlayer, rightPlayer, this->elements, parentNode);parentNode /= 2;return parentNode;}return 0;}template<typename T>inline int WinnerTree<T>::replayUpperInternalNode(int playerIndex, int parentNode){if (playerIndex > bottomExternalNodesNum){parentNode = (playerIndex - playerNum - 1 + 2 * startIndexOfBottomInternalNodes) / 2;if (parentNode * 2 > this->treeSize){int leftPlayer = parentNode * 2 - this->treeSize + bottomExternalNodesNum;int rightPlayer = leftPlayer + 1;comparePlayersAndSetInternal(leftPlayer, rightPlayer, this->elements, parentNode);parentNode /= 2;}}return parentNode;}template<typename T>inline int WinnerTree<T>::replayBorderInternalNode(int playerIndex, int parentNode){if (parentNode * 2 == this->treeSize){int leftPlayer = this->elements[parentNode * 2];int rightPlayer = bottomExternalNodesNum + 1;comparePlayersAndSetInternal(leftPlayer, rightPlayer, this->elements, parentNode);parentNode /= 2;}return parentNode;}template<typename T>inline void WinnerTree<T>::replayPureInternalNode(int parentNode){while (parentNode >= 1){int leftPlayer = this->elements[parentNode * 2];int rightPlayer = this->elements[parentNode * 2 + 1];comparePlayersAndSetInternal(leftPlayer, rightPlayer, this->elements, parentNode);parentNode /= 2;}}
6、获取胜者
template<typename T>inline int WinnerTree<T>::winner() const{if (this->treeSize == 0){throw std::overflow_error("no element in the tree");}return this->elements[1];}
