1 概述

竞赛树分为赢者树和输者树，赢者树更直观，输者树实现更高效。
比赛用二叉树来描述，每个外部节点表示一名选手，每个内部节点表示一场比赛，同一层内部节点代表一轮比赛，可以同时进行。



如果竞赛树是完全二叉树，则对于n个选手的比赛，最少的比赛场次为$log_2n$。
竞赛树不全是完全二叉树，但是完全二叉树可以是比赛的次数最少，竞赛树也成为选择树。

2 赢者树
2.1 定义

（1）赢者树：有n个选手的赢者树是一个完全二叉树，有n个外部节点和n-1个内部节点，每个内部节点记录的是该节点比赛的赢者。

分类：最大赢者树、最小赢者树（平局的时候左孩子选手获胜）

优点：当一个选手分数改变时，修改竞赛树比较容易。

2.2 抽象数据类型winnerTree

假设：选手个数一定，初始化后不能增减选手。

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


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

2.3 赢者树的实现

（1）表示



n名选手，n-1个内部节点分别对应数组player[1: n]，tree[1: n-1]

对于任何一个外部节点player[i]，其父节点tree[p]由以下公式给出：

$p=\left\{
\begin{aligned}
(i+offset)/2  &amp;&amp;&amp;&amp;&amp;&amp;  {i\leq lowExt } \\
(i-lowExt+n-1)/2  &amp;&amp;&amp;&amp;&amp;&amp;  {i &gt;lowExt}
\end{aligned}
\right.$

其中，$s=2^{|log_2(n-1)|}$、$offset=2*s-1$

（2）初始化

从右孩子开始，逐层往上，且每层从左往右依次考察右孩子选手。

（3）类completeWinnerTree
template<class T>
class completeWinnerTree : public winnerTree<T>
{
public:
	completeWinnerTree(T* thePlayer, int theNumberOfPlayers)
	{
		tree = NULL;
		initialize(thePlayer, theNumberOfPlayers);
	}
	~completeWinnerTree() { delete[] tree; }
	void initialize(T*, int);
	int winner() const
	{
		return tree[1];
	}
	int winner(int i) const
	{
		return (i < numberOfPlayers) ? tree[i] : 0;
	}
	// return winner of match at node i
	void rePlay(int);
	void output() const;
private:
	int lowExt;           // lowest-level external nodes
	int offset;           // 2^log(n-1) - 1
	int* tree;            // array for winner tree
	int numberOfPlayers;
	T* player;            // array of players
	void play(int, int, int);
};

3 总结
最先适配法求解箱子问题

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

竞赛树：

tournament tree, 也是以可完全二叉树，所以使用数组描述效率最好，竞赛树的基本操作是替换最大(小)元素

赢者树和输者树：



 

为了便于实现，需要将赢者树限制为完全二叉树。n个参与者的赢者树，具有n个外部节点，n-1个内部节点。每个内部节点记录的是在该节点比赛的赢者。

最大赢者树和最小赢者树：

为了确定输赢者，给每个选手一个分数，分数最大挥着最小的获胜，称为最大最小赢者树：



赢者树的初始化：

采用二叉树的后序遍历方法。每遍历一个节点，就相当于进行一场比赛。

排序：

内部排序法： 例如堆排序，插入排序，需要将排序的元素全部放入计算机内存进行排序，但是当待排序的元素数量超出内存的大小时，就需要使用外部排序。

外部排序步骤：

1. 生成一些初始的归并段（有序的部分待排序元素）

2. 合并这些归并段（利用赢者树）

C++实现赢者树：

假设用完全二叉树的数组表示赢者树，一棵赢者树有n个选手，则需要n-1个内部节点tree[1:n-1]，选手用数组player[1:n]表示。因此tree[i]是数组player的一个索引。

因此，必须确定外外部节点player[i]的父节点tree[P]。



选手个数n,内部节点个数n-1,最底层最左端的内部节点编号为2^s,其中s = 【log2(n-1)】, 最底层内部节点的个数n-s.最底层外部节点的个数lowExt = 2*(n-s),取offset = 2*s-1.则对于任何一个外部节点player[i], 其父节点tree[P]由以下公式给出：



赢者树的初始化：

为了初始化赢者树，需要从右孩子选手开始，进行他们所参加的比赛，而且逐层往上，只要是右孩子上升到比赛节点，就可以进行比赛。如在上图中，先进性p[2]的比赛，在进行p[3]的比赛得到结果t[2]，但是t[2]的比赛不能进行，因为它是左孩子，所以需要进行p[5]的比赛，得到t[3]，t[3]是右孩子，进行t[3]的比赛，得到t[1];

重新组织比赛：

当选手theplayer的值发生变化时，从外部节点player[theplayer]到根tree[1]的路径上，一部分或全部比赛都要重赛。

竞赛树的实现代码：

#ifndef TOURNAMENT_TREE_H
#define TOURNAMENT_TREE_H
#include <iostream>
#include <cmath>
using namespace std;

template<class T>
class completeWinnerTree
{
   public:
      completeWinnerTree(T *thePlayer, int theNumberOfPlayers)
      {
        tree = NULL;
        initialize(thePlayer, theNumberOfPlayers);
      }
      ~completeWinnerTree() {delete [] tree;}
      void initialize(T*, int);
      int winner() const//返回赢者树的根节点。
      {
	  		return tree[1];
	  }
      int winner(int i) const//返回第i个节点的胜者
      {
	  		return (i < numberOfPlayers) ? tree[i] : 0;
	  }
         // return winner of match at node i
      void rePlay(int);
      void output() const;
   private:
      int lowExt;           // lowest-level external nodes
      int offset;           // 2^log(n-1) - 1
      int *tree;            // array for winner tree
      int numberOfPlayers;
      T *player;            // array of players
      void play(int, int, int);
};



template<class T>
void completeWinnerTree<T>::play(int p, int leftChild, int rightChild)
{
	// play matches beginning at tree[p]
 	// leftChild is left child of p
 	// rightChild is right child of p
	//如果左节点的数据较小则左节点晋级。
   	tree[p] = (player[leftChild] <= player[rightChild]) ?
                   leftChild : rightChild;

   // more matches possible if at right child
   while (p % 2 == 1 && p > 1)//如果当前节点是右节点，且不是根节点，那么继续进行比赛。
   {// at a right child
      tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ?tree[p - 1] : tree[p];
      p /= 2;    // go to parent
   }
}


template<class T>
void completeWinnerTree<T>::initialize(T *thePlayer, int theNumberOfPlayers)
{
	// Create winner tree for thePlayer[1:numberOfPlayers].
	//比赛参与者最少2个人否则报错
   	int n = theNumberOfPlayers;
   	if (n < 2)
   	{
      //throw illegalParameterValue("must have at least 2 players");
	  cout << "The players must > 2" << endl;
	  exit(0);
	   	
    }
   	player = thePlayer;//获取外节点数组。
   	numberOfPlayers = n;
   	delete [] tree;//初始化树节点，因为第0位置不放数据，所以实际大小为n-1.
   	tree = new int [n];//

    // compute  s = 2^log (n-1)
   	int i, s;//计算内部节点最左边的节点编号，下面采取寻访方式计算s，非常巧妙
   	for (s = 1; 2 * s <= n - 1; s += s);

   	lowExt = 2 * (n - s);//计算最低层外部节点的个数
   	offset = 2 * s - 1;

    // play matches for lowest-level external nodes
   	for (i = 2; i <= lowExt; i += 2)//首先进行最底层外部节点的比赛，i从2开始且每次+2是为了每次都是从右子节点开始进行比赛
      	play((offset + i) / 2, i - 1, i);

   	// handle remaining external nodes
   	if (n % 2 == 1)//如果倒数第二层最左边的元素为某个父节点的右节点，则进行如下处理，即比赛。
   	{// special case for odd n, play internal and exteral node
    	  play(n/2, tree[n - 1], lowExt + 1);
      	i = lowExt + 3;//然后从lowExt+3即倒数第二层外部节点的右儿子开始比赛
   	}
   	else i = lowExt + 2;//否则右儿子为lowExt+2

   // i is left-most remaining external node
   	for (; i <= n; i += 2)//然后开始处理倒数第二层其他外部节点。
     	 play((i - lowExt + n - 1) / 2, i - 1, i);//play每次都会处理到上层的左节点为止，然后再去处理下一个右节点。
}



template<class T>
void completeWinnerTree<T>::rePlay(int thePlayer)
{// Replay matches for player thePlayer.
   int n = numberOfPlayers;
   if (thePlayer <= 0 || thePlayer > n)//改变的选手必须要在范围内。
   {
   		cout << "Invalid index" << endl;
   		exit(0);
   }
      //throw illegalParameterValue("Player index is illegal");

   int matchNode,       // node where next match is to be played需要重赛的父节点
       leftChild,       // left child of matchNode该父节点的左孩子
       rightChild;      // right child of matchNode右孩子

   // find first match node and its children
   if (thePlayer <= lowExt)//如果改变的参数在最低层
   {
      // begin at lowest level
      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;

   // special case for second match
   if (matchNode == n - 1 && n % 2 == 1)//这里没弄明白。。。
   {
      matchNode /= 2;   // move to parent
      tree[matchNode] = (player[tree[n - 1]] <=
                         player[lowExt + 1]) ?
                        tree[n - 1] : lowExt + 1;
   }

   // play remaining matches
   matchNode /= 2;  // move to parent
   for (; matchNode >= 1; matchNode /= 2)//依次往上进行重赛直到主节点。
      tree[matchNode] = (player[tree[2 * matchNode]] <=player[tree[2 * matchNode + 1]])?tree[2 * matchNode] : tree[2 * matchNode + 1];
}


template<typename T>
void completeWinnerTree<T>::output() const
{
	cout << "number of players: " << numberOfPlayers << endl;
	cout << "lowExt = " << lowExt << endl;
	cout << "offset = " << offset << endl;
	for(int i=1; i<numberOfPlayers; i++)
	{
		cout << tree[i] << " ";
	} 
	cout << endl;
}

#endif




代码来源：https://www.cise.ufl.edu/~sahni/dsaac

搜索树

搜索树适用于字典描述，与跳表和散列相比，二叉搜索树和平衡搜索树使用更加灵活，在最坏的情况下性能有保证。

二叉搜索树：

是一棵二叉树，可能为空，非空的二叉搜索树满足以下特征：

1.每个元素都有唯一的关键字

2.根节点的左子树中，元素的关键字都小于根节点的关键字

3.根节点的右子树中，元素的关键字都大于根节点的关键字

4.根节点左右子树也都是二叉搜索树



a就不是二叉搜索树（不满足4），bc是二叉搜索树。

注： 有重复值的二叉搜索树， 小于-->小于等于

索引二叉搜索树：

源于普通的二叉搜索树，只是在每个节点中添加一个leftSize域，表示该节点的左子树的元素个数：



二叉搜索树的操作：

1. 搜索：

假设需要查找的关键字为theKey,则先从根节点开始查找，如果为空，则树不包含任何元素；否则，将theKey和根节点的关键字进行比较，如果等于，则查找成功，如果theKey小于根节点的关键字，则查找左子树即可，否则，查找右子树。

2. 插入

假设要在二叉搜索树中插入一个元素，首先通过查找来确定，要插入的元素的关键字在树中是否存在，如果存在，则用插入元素的value覆盖掉原来的value，否则，将元素插入树中：

3. 删除

要考虑三种情况：

1.要删除的节点是树叶： 

2.要删除的节点有一棵子树

3.要删除的节点有两棵子树

二叉搜索树的实现;

// 定义二叉搜索树树
#ifndef BSTREE_H
#define BSTREE_H
#include <algorithm> 
#include <iostream>
using namespace std;

// 定义二叉搜索树的节点
template<typename K=int, typename V=int>   // key: value类型的节点 
struct BSTreeNode
{
	BSTreeNode* leftchild;
	BSTreeNode* rightchild;
	K key;
	V value;
	
	BSTreeNode(K& theKey, V& theValue)
	{
		key = theKey;
		value = theValue;
		leftchild = NULL;
		rightchild = NULL;
	}
}; 

template<typename K, typename V>
class BSTree
{
	typedef BSTreeNode<K, V> BSTreeNode;
	private:
	BSTreeNode* root;     // 二叉搜索树的根节点
	int treeSize;
	void destory(BSTreeNode* mroot);       // 删除二叉树的所有节点  // 析构函数 
	BSTreeNode* find(K theKey, BSTreeNode* mroot); 
	void insert(K theKey, V theValue, BSTreeNode* mroot);
	void remove(K theKey, BSTreeNode* mroot); // 删除特定的节点 
	void out_put(BSTree* mroot);
	 
	public:
	BSTree();
	~BSTree();
	// void destory(); 
	// 查找二叉树的节点
	BSTreeNode* find(K theKey);  // 参数：键值
	void insert(K theKey, V theValue);
	void remove(K theKey); 
	void out_put();
};

template<typename K, typename V>
void BSTree<K, V>::destory(BSTreeNode* mroot)
{
	// 删除所有节点   递归调用 
	if(mroot!=NULL)
	{
		destory(mroot->leftchild);
		destory(mroot->rightchild);
		delete mroot;
	}	 
}


template<typename K, typename V>
BSTree<K, V>::BSTree()
{
	treeSize = 0;
	root = NULL;
}

template<typename K, typename V> 
BSTree<K, V>::~BSTree()
{
	// 删除二叉树的节点
	destory(root); 
}

template<typename K, typename V>
BSTreeNode* BSTree<K, V>::find(K theKey)
{
	// 二叉搜索树的查找函数
	// 根据关键字查找：
	return find(theKey, root); 
}

template<typename K, typename V>
BSTreeNode* BSTree<K, V>::find(K theKey, BSTreeNode* mroot)
{
	if(mroot != NULL)
	{
		if(mroot->key==theKey)
		{
			return mroot;
		}
		else if(mroot->key>theKey)   // 搜索左子树
		{
			return find(theKey, mroot->leftchild);    // 递归的方法 
		} 
		else   // 搜索右子树
		{
			return find(theKey, mroot->rightchild);
		} 
	}
	return NULL;  // 没有找到 
}

template<typename K, typename V>
void BSTree<K, V>::insert(K theKey, V theValue, BSTreeNode* mroot)
{
	// NULL
	
	if(mroot==NULL)
	{
		mroot = new BSTreeNode(theKey, theValue);
		return;    // 递归结束    
	}
	
	if(mroot->key==theKey)   // 关键字已经存在 
	{
		mroot->value = theValue;
		return;    // 结束递归 
	} 
	else if(theKey < mroot->key)    // 插入左子树
	{
		insert(theKey, theValue, mroot->leftchild);
	} 
	
	else   // 插入右子树 
	{
		insert(theKey, theValue, mroot->rightchild); 
	}
	
}

template<typename K, typename V>
void BSTree<K, V>::insert(K theKey, V theValue)
{
	insert(theKey, theValue, root);
}

template<typename K, typename V>
void BSTree<K, V>::remove(K theKey, BSTreeNode* mroot)
{
	/* 
	if(mroot==NULL)   // 结束的条件 
	{
		cout << "No such node" << endl; 
		return;
	}
	*/
	 
	// 只有一个节点
	if(mroot->leftchild==NULL && mroot->rightchild==NULL)   // 最底层的节点 
	{
		if(root->key==theKey)   // 是要查找的节点 
		{
			delete mroot;
			mroot = NULL;
			return;
		}
		
	}
	
	if(theKey<mroot->key)    // 搜索左子树 
	{
		remove(theKey, mroot->leftchild); 
	} 
	else if(theKey>mroot->key)
	{
		remove(theKey, mroot->rightchild);   // 搜索右子树 
	}
	else     // 相等。且不是最底层的节点  
	{
		BSTreeNode* del = NULL;    // 临时的指针
		if(mroot->leftchild==NULL)   // 只有右孩子 
		{
			del = mroot;
			mroot = mroot->rightchild;   // 取右孩子
			delete del;
			del = NULL;
			return; 
		} 
		else if(mroot->rightchild==NULL)   // 只有左孩子
		{
			del = mroot;
			mroot = mroot->leftchild;
			delete del;
			del = NULL;
			return;
		}
		else   // 要删除的节点有左右子树 
		{
			BSTreeNode* rightFirst = mroot->rightchild;   // 获取要删除的节点的右孩子
			while(rightFirst->leftchild!=NULL)
			{
				rightFirst = rightFirst->leftchild;
			} 
			
			// 交换
			// 将要删除的节点交换到最底层 
			swap(mroot->key, rightFirst->key);
			swap(mroot->value, rightFirst->value); 
			remove(theKey, mroot->rightchild);     // 接着删除
		    return;   // ? 
		} 
	} 
	
}

template<typename K, typename V>
void BSTree<K, V>::remove(K theKey)
{
	remove(theKey, root);
}

template<typename K, typename V>
void BSTree<K, V>::out_put(BSTreeNode* mroot)
{
	if(mroot==NULL)
	{
		return;
	}
	out_put(mroot->leftchild);
	cout << "key: " << mroot->key << " value: " << mroot->value << " ";
	out_put(mroot->rightchild);
}

template<typename K, typename V>
void BSTree<K, V>::out_put() 
{
	out_put(root);
} 

#endif


 

一、竞赛树
         假设有n个选手参加一场网球比赛，比赛规则是“突然死亡法”，即只要输一场就会被淘汰。一对一进行比拼，最后只剩下一个选手保持不败。下图13-1中显示了比赛过程，有a~h一共8名选手。这个比赛使用二叉树进行表示，每一个外部节点表示一名选手，每一个内部节点表示一场比赛，该节点的孩子表示比赛的选手。在同一层的内部节点代表一轮比赛，可以同时进行。在第一轮比赛中，对阵的选手有ab之间、cd之间、ef之间以及gh之间。每一场比赛的胜利者被记录在代表该比赛的内部节点中。在下图a中，第一轮比赛的胜利者为b、d、e和h，其余四位选手直接淘汰；下一轮比赛的对阵是bd之间、eh之间，胜利者是b和e，并且进入决赛；最后胜利者是e，放在根节点上。整个比赛过程见图a所示。图b中给出5名选手参加的比赛，从a到e，最后的胜利者是c。
         
       上图的两颗树都是完全二叉树。现实中竞赛所对应的树不一定是完全二叉树，但是这样做会使得比赛的场次最少。而且上面的竞赛树每一个内部节点记录的是比赛的赢者，我们称之为赢者树。如果内部节点记录的是比赛的输者，我们称之为输者树。应用中赢者树更加直观，但是输者树的实现效率更高。
       我们定义赢者树：有n个选手的一颗赢者树是一颗完全二叉树，它有n个外部节点和n-1个内部节点，每一个内部节点记录的是在该节点进行比赛的胜利者。我们定义最小赢者树，每一场比赛分数少的选手获胜；最大赢者树中，每一场比赛分数多的选手获胜。在分数相等时，左孩纸表示的选手获胜。下图13-2中a是一颗有8名选手的最小赢者树，b是一颗有5名选手的最大赢者树。每一个外部节点下面的数字表示选手的分数。
        
二、赢者树
       我们使用完全二叉树的数组表示赢者树。一颗赢者树有n名选手，需要n-1个内部节点 tree[1:n-1]。选手或者外部节点用数组 player[1:n] 表示，因此 tree[i] 是数组player的一个索引，类型为int。在赢者树的节点 i 对应比赛中的赢者 tree[i] 。图13-4给出在5个选手的赢者树中，各节点与数组 tree 和 player 之间的对应关系。
       
      为实现这种对应关系，我们必须能够确定外部节点 player[i]  的父节点 tree[p]。当外部节点的个数为n时，内部节点的个数为n-1。最低层最左端的内部节点，其编号为s，并且有s=2^log（n-1）。因此，最底层内部节点的个数为n-s，而最底层外部节点的个数lowExt是这个数的2倍。例如，在图13-4中，n=5，s=4，最底层最左端的内部节点是 tree[4]，这一层的内部节点个数为n-4=1个。最底层外部节点个数lowExt=2，倒数第二层最左端的外部节点编号是lowExt+1.。令offset=2*s-1。对于任何一个外部节点
 player[i] ，其父节点tree[p]有一下公式给出：
      
      赢者树关键的两个操作是初始化和重新组织比赛。为了初始化一个赢者树，我们从右孩纸选手开始，进行他所参加的比赛，而且逐层网上，只要是从右孩纸上升到比赛节点，就可以进行在该节点的比赛。为此，要从左往右的考察右孩纸选手。在图13-4的树种，我们首先进行选手 player[2] 的比赛，然后进行 player[3] 的比赛，最后进行 player[5]的比赛。首先，我们进行选手 player[2] 参加在节点 tree[4]  的比赛，但是接下来，我们不能在上一层节点 tree[2]  的比赛，因为
 tree[4] 是左孩纸。然后我们进行选手 player[3] 参加在tree[2] 的比赛，但是接下来不能进行在节点tree[1]的比赛，因为tree[2]是左孩纸。最后我们进行选手 play[5] 参加的在节点tree[3]的比赛和在节点 tree[1] 的比赛。注意，节点 tree[i] 节点记录的是比赛的赢者。
      当选手 thePlayer 的值改变，在从外部节点 player[ thePlayer ] 到根节点 tree[1] 的路径上，一部分或者全部比赛都需要进行重赛。为简单起见，我们要路径上的全部比赛重赛。具体的实现方案如下：
三、赢者树的实现

#pragma once 
#include<iostream>

using namespace std;

template <class T>
class winnerTree
{
public:
	//构造函数和析构函数
	winnerTree(T* thePlayer, int theNumberOfPlayer)
	{
		tree = NULL;
		initializer(thePlayer, theNumberOfPlayer);
	}
	~winnerTree(){ delete[] tree; }

	//使用数组thePlayer初始化一个赢者树
	void initializer(T *, int );
	//返回比赛最后赢者的下标
	int winner() const { return tree[1]; }
	//返回比赛中某一环节的比赛的赢者
	int winner(int i) const { return (i < numberofPlayer) ? tree[i] : 0; }
	//因改变某一个player的值进而重赛
	void rePlay(int);
	//输出
	void output() const;

private:
	T* player;//参赛成员组成的数组
	int numberofPlayer;//参赛成员的数量
	int* tree;//赢者树，数组表示，赢者树只包含比赛结果，节点表示赢者的下标

	int lowExt;//用于生成赢者树，表示最底层外部节点的个数
	int offset;//用于生成赢者树，=2^log(n-1) - 1，详见解析
	void play(int, int, int);//初始化需要用到，
};

//使用数组thePlayer初始化为一个赢者树
template<class T>
void winnerTree<T>::initializer(T *thePlayer, int theNumberOfPlayers)
{
	int n = theNumberOfPlayers;
	if (n < 2)
	{
		cerr << "Must have at least 2 players"; exit(0);
	}

	player = thePlayer;
	numberofPlayer = n;
	delete[] tree;
	tree = new int[n];//n个外部节点，需要n-1内部节点，而数组0空置不用，所以需要n的空间

	int s;
	for (s = 1; 2 * s <= n - 1; s += s);//最底层最左端的内部节点编号s = 2^log (n-1),取log的下整
	lowExt = 2 * (n - s);//最底层外部节点个数=2*最底层内部节点个数，最底层内部节点个数n-s
	offset = 2 * s - 1;//令offset=2*s-1
	//对于任何一个外部节点player[i]，其父节点tree[p]满足：
	//当i<=lowExt时，p=(i+offset)/2;  当i>lowExt时，p=(i-lowExt+n-1)/2;
	
	int i;
	//对最底层的外部节点比赛，从2，4，6。。开始知道判断
	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//如果外部节点n为偶数
		i = lowExt + 2;
	for (; i <= n; i += 2)
		play((i - lowExt + n - 1) / 2, i - 1, i);
}

//play操作，从最开始的底层进行比赛，直到完成所有比赛决胜出最后赢者
template<class T>
void winnerTree<T>::play(int p, int leftchild, int rightchild)
{//从tree[p]开始的比赛，一直往上冒泡，直至根节点
	tree[p] = (player[leftchild] <= player[rightchild]) ? leftchild : rightchild;
	while (p % 2 == 1 && p > 1)
	{//p作为右孩纸出现，才继续往上走，因为最开始play中也是由右孩纸判断的
		tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ? tree[p - 1] : tree[p];
		p /= 2;
	}
}

//当thePlayer的值改变时，需要重赛,我们可以打乱然后重新初始化，但一般不这么做
template<class T>
void winnerTree<T>::rePlay(int thePlayer)
{
	int n = this->numberofPlayer;
	if (thePlayer <= 0 || thePlayer > n)
	{
		cerr << "Player index is illegal"; exit(0);
	}
	int matchNode,leftchid,	rightchild;//下一个需要重赛的节点以及他的孩纸

	//找出第一个需要重赛的节点以及他的左右孩纸
	if (thePlayer <= lowExt)
	{
		matchNode = (offset + thePlayer) / 2;
		leftchid = 2 * matchNode - offset;
		rightchild = leftchid + 1;
	}
	else
	{
		matchNode = (thePlayer - lowExt + n - 1) / 2;
		if (2 * matchNode == n - 1)
		{
			leftchid = tree[2 * matchNode];
			rightchild = thePlayer;
		}
		else
		{
			leftchid = 2 * matchNode - n + 1 + lowExt;
			rightchild = leftchid + 1;
		}
	}
	tree[matchNode] = (player[leftchid] <= player[rightchild]) ? leftchid : rightchild;

	//第二个需要重赛的节点中的特殊情况，即包含内部和外部节点
	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];
}

//输出
template<class T>
void winnerTree<T>::output() const
{
	cout << "number of players  = " << numberofPlayer
		<< " lowExt = " << lowExt
		<< " offset = " << offset << endl;
	cout << "complete winner tree pointers are" << endl;
	for (int i = 1; i < numberofPlayer; i++)
		cout << tree[i] << ' ';
	cout << endl;
}


   测试代码：


#include <iostream>
#include "WinnerTree.h"
using namespace std;

struct player
{
	int id, key;

	operator int() const { return key; }
};

void main(void)
{
	int n;
	cout << "Enter number of players, >= 2" << endl;
	cin >> n;
	if (n < 2)
	{
		cout << "Bad input" << endl;
		exit(1);
	}


	player *thePlayer = new player[n + 1];

	cout << "Enter player values" << endl;
	for (int i = 1; i <= n; i++)
	{
		cin >> thePlayer[i].key;
		thePlayer[i].id = i;
	}

	winnerTree<player> *w =	new winnerTree<player>(thePlayer, n);
	cout << "The winner tree is" << endl;
	w->output();

	thePlayer[2].key = 0;
	w->rePlay(2);
	cout << "Changed player 2 to zero, new tree is" << endl;
	w->output();
}



四、输者树
       输者树的内部节点记录的是比赛的失败者，我们可以使用 tree[0] 来记录比赛最后的赢者。当一个赢者发生变化，使用输者树可以简化重新比赛的过程。但是，其他选手发生改变时，还是使用赢者树比较方便，毕竟赢者树在概念上更容易理解。因此，只有选手 player[i] 为前一次比赛的赢家时，对于函数 rePlay（i）采用输者树比赢者树执行效率高。

竞赛树
竞赛树的基本操作是替换最大（或最小）元素。如果有n个元素，这个基本操作的用时为O(logn).。虽然用堆和左高树来表示也能用近似的时间（O(logn)）完成这个操作，但是用来实现可预见的断连操作都不容易。当我们需要按指定的方式断开连接时，比如选择最先插入的元素，或选择左端元素（假定每个元素都有一个从左到右的名次），这时，竞赛树就成为我们要选择的数据结构。