精华内容
下载资源
问答
  • 数据结构与算法——竞赛树

    千次阅读 2019-05-28 10:12:21
    1 概述 竞赛树分为赢者树和输者树,赢者树更直观,输者树实现更高效。 比赛用二叉树来描述,每个外部...竞赛树不全是完全二叉树,但是完全二叉树可以是比赛的次数最少,竞赛树也成为选择树。 2 赢者树 2.1 定义 ...

    1 概述

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

    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 = { ( 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 &gt; l o w E x t 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. p={(i+offset)/2(ilowExt+n1)/2ilowExti>lowExt
    其中, s = 2 ∣ l o g 2 ( n − 1 ) ∣ s=2^{|log_2(n-1)|} s=2log2(n1) o f f s e t = 2 ∗ s − 1 offset=2*s-1 offset=2s1
    (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 总结

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

    展开全文
  • 数据结构学习笔记(七)竞赛树

    千次阅读 2016-07-30 21:22:37
    竞赛树,赢者树,输者树
    一、竞赛树

             假设有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个元素,这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树...
    
    

    一、竞赛树概述

    • 竞赛树是完全二叉树(或满二叉树)
    • 竞赛树可以用数组来表示,而且存储效率最高
    • 竞赛树的基本操作是替换最大(或最小)元素。如果有n个元素,这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树来表示也能用近似的时间(O(logn))完成这个操作,但是用来实现可预见的断接操作都不容易
    • 当我们需要按指定的方式断开连接时,比如选择最先插入的元素,或选择左端元素(假定每个元素都有一个从左到右的名次),这时,竞赛树就成为我们要选择的数据结构
    • 竞赛树也称为选择树
    • 竞赛树一般分为:赢者树、输者树

    二、赢者树概述

    什么是赢者树?

    • 假设有n个选手参加一次网球比赛。比赛规则是“突然死亡法”:一名选手只要输掉一场球,就被淘汰。一对一选手比较,最终只剩下一个选择保持不败。这个“辛存者”就是比赛赢者
    • 下图显示了一次网球比赛:
      • 有8名选手参加,从a和h
      • 这个比赛用二叉树来描述,每个外部节点表示一名选手每个内部节点表示一场比赛(该节点的孩子表示比赛的选手
      • 在同一层的内部节点代表一轮比赛,可以同时进行
      • 下图中,第一轮比赛中,对阵的选手有4对:a与b、c与d、e与f、g与h,第一轮比赛的赢者为b、d、e、h;下一轮比赛的对阵是b和d、e和h,并且进入决赛;最终赢者为e

    • 下图也表示一场比赛,最终的赢者是c

    • 赢者树概念:通过上面的演示案例我们可以知道,赢者树就是每一个内部节点所记录的都是比赛的赢者
    • 有n个选手一棵赢者树是一棵完全二叉树,它有n个外部节点和n-1个内部节点,每个内部节点记录的是在该节点比赛的赢者

    最大赢者树、最小赢者树(附:平局)

    • 最大赢者树:分数大的选手获胜
    • 最小赢者树:分数最小的选手获胜
    • 不论是最大赢者树还是最小赢者树,当分数相等,平局的时候,左孩子表示的选手获胜

    赢者树的初始化

    • n个选手的赢者树可以在Θ(n)时间内初始化
    • 方法是:
      • 沿着从叶子到根的方向,在内部节点进行n-1场比赛
      • 也可以采用后序遍历来初始化,每访问一个节点,就进行一场比赛

    赢者树的重构

    • 当一个节点的分数发生变化时,需要将赢者树进行重构
    • 有一颗n个选手的赢者树中,当一个选手的分数发生变化时,需要修改的比赛场次介于之间,因此,赢者树的重构需耗时O(\logn\log n)

    赢者树的排序

    • 步骤:
      • 我们假设对最小赢者树进行排序(那么最终的赢者就是关键字值最小的元素)
      • 我们在所有的元素中选出关键字最小的元素,将该元素的关键字值改为最大值(假设为),使它赢不了剩余的其它任何选手
      • 然后重构赢者树,这时的总冠军是排序在第二的元素。同样的道理,将该元素的关键字也改为最大值(假设为),使它也赢不了剩余的其它任何选手
      • 依次类推,再一次重构赢者树......最终就可以完成n个元素的排序
    • 复杂度:
      • 赢者树初始化的用时为Θ(n)。每次改变赢者的关键字并重构赢者树的用时为Θ(\log n),因为在从一个外部节点到根的路径上,所有的比赛需要重赛。赢者树的重构共需n-1次。因此,整个排序过程的时间为Θ(n+n\log n)=Θ(n\log n)

    初始归并段的生成(外部排序)

    • 目前为止,我们所讨论的排序方法(插入排序、堆排序等)都是内部排序法。这些方法要求待排序的元素全部放入一计算机内存。但是,当待排序的元素所需要的空间超出内存的容量时,内部排序法就需要频繁地访问外部存储介质(如磁盘),那里存储着部分或全部待排的元素。这使得排序效率大打折扣。于是我们需要引入外部排序法
    • 外部排序一般包括两个步骤:

      • 1.生成一些初始归并段(run),每一个初始归并段都是有序集
      • 2.将这些初始归并段合并为一个归并段

    演示案例

    • 假设待排序的记录有16000个,使用内部排序一次最多可排序1000个记录
    • 步骤如下:
      • 1.重复下面操作16次,得到16个初始归并段
        • 输入1000个记录
        • 用内部排序法对这1000个记录排序
        • 输出排序结果,即归并段
      • 2.开始合并归并段:在这个步骤中,我们进行若干次归并。每一次归并都是将最多k个归并段合并为一个归并段,归并段耳朵个数也因此讲到归并前的1/k。这个过程持续到归并段的个数等于1为止
    • 本例有16个初始归并段。它们的编号分别为R1、R2......R16:
      • 在第一次归并中,先将R1~R4合并为S1,其长度为4000个记录,然后将R5~R8合并,以此类推
      • 在第二次归并中,将S1~S4合并为T1,它是外部排序的最终结果

    合并归并段的方法解析

    • 合并k个归并段的方法是:
      • 从k个输入归并段的前面,不断把关键字最小的元素移到正在生成的输出归并段
      • 当所有元素从k个输入归并段移至输出归并段时,合并过程就完成了
    • 注意:在选择输出归并段的下一个元素时,在内存中只需要知道每个输入归并段的首元素的关键字即可。因此,只要有足够的内存来保存k个关键字,就可以完成k个任意长度的归并段。但是在实际应用上,我们需要每一次能输入/输出很多元素,以减少输入/输出的次数
    • 以上面的演示案例为例:
      • 在上列待排的16000个记录中,每个归并段有1000个记录,而内存容量也是1000个记录
      • 为了合并前4个归并段,可将内存分为5个缓冲区,每个缓冲区的容量为200个记录。前4个为输入缓冲区,第5个为输出缓冲区
      • 从前4个输入归并段各取200个记录放入4个输入缓冲区。把合并的记录放入输出缓冲区。不断把输入缓冲区合并后放入输出缓冲区,直到以下的一个条件满足为止:
        • 1.输出缓冲区已满
        • 2.某一输入缓冲区变空
      • 当第一个条件满足时,将输出缓冲区的记录写入磁盘,写完之后继续合并
      • 当前两个条件满足时,从空缓冲区所对应的输入归并段继续读取记录,读取过程结束之后,继续合并
      • 当4000个记录都写入一个归并段S1时,前4个归并段的合并过程结束

    复杂度分析

    • 在归并段合并中,决定时间的因素之一是在步骤1(“输出缓冲区已满”)中生成的初始归并段的个数。使用赢者树可以减少初始归并段的个数
    • 假设一棵赢者树有p名选手,其中每个选手是输入集合的一个元素,它有一个关键字和一个归并段号
    • 前p个元素的归并段号均为1
    • 当两个选手进行比赛时,归并段号小的选手获胜;在归并段号相同时,关键字小的选手获胜
    • 为生成初始归并段,重复地将总冠军W移动它的归并号所对应的归并段,并用下一次输入元素N取代W
      • 如果N的关键字大于等于W的关键字,则令元素N的归并段号与W的相同,因为在W之后把N输出到同一归并段不会影响归并段的持续
      • 如果N的关键字小于W的关键字,则令元素N的归并号为W的归并段号加1,因为在W之后吧把N输出同一个归并段将破坏归并段的排序

    初始归并段的长度

    • 当采用上述方法生成初始归并段时,初始归并段的平均长度约为2p
    • 当2p大于内存容量时,我们希望能得到更少的初始归并段(与上述方法相比)
    • 事实上,倘若输入集合已经有序(或几乎有序),则只需生成最后的归并段,这样可以跳过归并段的合并,即步骤2(“某一输入缓冲区变空”)

    k路合并

    • 在k路合并(上面的初始归并段)中,k个归并段合并成一个归并段
    • 按照上面所述的方法,每一个元素合并到输出归并段所需的时间为O(k),因为每一次迭代都需要在k个关键字中找到最小值。因此,产生一个大小为n的归并段所需要的总时间为O(kn)
    • 使用赢者树可将这个时间缩短为Θ(k+nlogk):
      • 首先用Θ(k)的时间初始化一棵有k个选手的赢者树,这k个选手分别是k个归并段的头元素
      • 然后将赢者移入输出归并段,并从相应的输入归并段中取出下一个元素替代赢者的位置
      • 若该输入段无下一个元素,则用一个关键字值很大(例如)的元素替代。这个提取和替代赢家的过程需要n次,一次需要时间为Θ(logk)
      • 一次k路合并的总时间为Θ(k+nlogk)

    三、竞赛树的抽象数据类型(ADT)

    • 我们定义的抽象数据类型为WinnerTree
    • 我们假设选手的个数是固定的。也就是说,如果初始化时的选手个数为n,那么初始化之后不能再增减选手
    • 选手本身并不是赢者树的组成部分,组成赢者树的成分是内部节点
    • 赢者树支持的操作有:
      • 初始化一棵具有n名选手的赢者树
      • 返回赢者
      • 重新组织从选手i到根的路径上的比赛

    四、竞赛树的抽象类

    • 根据抽象数据模型,我们定义了下面的抽象类
    #include "main.h"
    
    template<class T>
    class winnerTree
    {
    public:
    	virtual ~winnerTree() {}
    
    	//用数组thePlayer[1:numberOfPlayers]生成赢者树
    	virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;
    
    	//返回赢者的索引
    	virtual int winner()const = 0;
    
    	//在参赛者thePLayer的分数变化后重赛
    	virtual void rePlay(int thePLayer) = 0;
    };

    五、赢者树的编码实现

    赢者树的数组表示

    • 假设用完全二叉树的数组来表示赢者树
    • 一棵赢者树有n名选手,需要n-1个内部节点。选手用player数组来表示,赢者树节点用tree数组来表示
    • 下图给出了在有5个选手的赢者树中,各节点与数组tree和player之间的对应关系

    数组与索引的关系

    • 为了实现上面的对应关系,我们必须能够确定外部节点player[i]的父节点tree[p]
    • 当外部节点的个数为n时:
      • 内部节点的个数为n-1
      • 最底层最左端的内部节点,其编号为s,且s=
      • 因此,最底层内部节点的个数为n-s,最底层外部节点个数lowExt是这个数的2倍
    • 例如,在上图中:
      • n=5,s=4,最底层最左端的内部节点时tree[4],这一层的内部节点个数为n-4=1个
      • 最底层外部节点个数lowExt=2,倒数第2层最左端的外部节点号为lowExt+1
    • 令offset=2*s-1,对于任何一个外部节点player[i],其父节点tree[p]由以下公式给出:

    赢者树的初始化

    • 原理:为了初始化一棵赢者树,我们从右孩子选手开始,进行他所参数的比赛,而且逐层往上,只要是从右孩子上升到比赛节点,就可以进行在该节点的比赛。为此,要从左往右地考察右孩子选手
    • 在下图中:
      • 在下面的步骤中,我们会依次进行选手player[2]参加的比赛,然后进行选手player[3]参加的比赛,最后进行选手player[5]参加的比赛
      • 首先,我们进行选手player[2]参加的在节点tree[4]的比赛
      • 但是接下来,我们不能进行在上一层节点tree[2]的比赛,因为tree[4]是它的左孩子
      • 然后我们进行选手player[3]参加的在节点tree[2]的比赛,但是接下来不能进行在节点tree[1]的比赛,因为tree[2]是它的左孩子
      • 最后我们进行选手player[5]参加的在节点tree[3]的比赛和在节点tree[1]的比赛
      • 注意,当在节点tree[i]进行比赛时,参加该比赛的选手已经确定,而且选手的记录已经存储在节点tree[i]的子节点中

    重新组织比赛

    • 当选手thePlayer的值改变时,在从外部节点player[thePlayer]到根tree[1]的路径上,一部分或全部比赛都需要重赛
    • 为简单起见,我们将该路径上的全部比赛进行重赛
    • 实际上,在上面的例子中,改变的只是赢者的值
    • 一个赢者的值改变了,必然会导致从赢者对应的外部节点到根的路径上的所有比赛要重赛

    编码实现

    • 下面我们实现一个最小赢者树
    • 抽象类定义如下:
    #ifndef WINNERTREE_H_
    
    #include "main.h"
    
    template<class T>
    class winnerTree
    {
    public:
    	virtual ~winnerTree() {}
    
    	//用数组thePlayer[1:numberOfPlayers]生成赢者树
    	virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;
    
    	//返回最终赢者的索引
    	virtual int winner()const = 0;
    
    	//在参赛者thePLayer的分数变化后重赛
    	virtual void rePlay(int thePlayer) = 0;
    };
    
    #endif
    • 赢者树定义:
      • 方法winner的时间复杂性是O(1)。initialize的时间复杂性为O(n),rePlay的时间复杂性是O(logn)。其中n是竞赛选手个数
    #ifndef COMPLETEWINNERTREE_H_
    
    #include "main.h"
    #include "myExceptions.h"
    #include "winnerTree.h"
    
    template<class T>
    class completeWinnerTree :public winnerTree<T>
    {
    public:
    	completeWinnerTree(T *thePlayer, int theNumerOfPlayers) {
    		//构造函数,将赢者树初始化为空,然后生成赢者树
    		this->tree = nullptr;
    		initialize(thePlayer, theNumerOfPlayers);
    	}
    	~completeWinnerTree() {
    		//析构函数
    		if (tree) {
    			delete[] tree;
    		}
    		tree = nullptr;
    	}
    
    	//用数组thePlayer[1:numberOfPlayers]生成赢者树
    	void initialize(T *thePlayer, int theNumberOfPlayers)override;
    	//返回最终赢者的索引
    	int winner()const override { return this->tree[1]; }
    	//返回竞赛树某个节点的赢者
    	int winner(int i) const{
    		return (i < this->numberOfPlayers) ? this->tree[i] : 0;
    	}
    	//在参赛者thePLayer的分数变化后重赛
    	void rePlay(int thePlayer)override;
    
    	//输出赢者树中的一些信息
    	void output()const;
    private:
    	/*
    		对tree[p]节点进行比赛,leftChild为左子节点,rightChild为右子节点
    		如果还有父节点,继续向上比赛
    	*/
    	void play(int p, int leftChild, int rightChild);
    private:
    	int lowExt;         //最底层外部节点个数
    	int offset;         //offset=2*s-1(s为最底层最左端的内部节点)
    	int *tree;          //赢者树
    	int numberOfPlayers;//竞赛选手的数量
    	T *player;          //保存竞赛选手
    };
    
    //用数组thePlayer[1:numberOfPlayers]生成赢者树
    template<class T>
    void completeWinnerTree<T>::initialize(T *thePlayer, int theNumberOfPlayers)
    {
    	int n = theNumberOfPlayers;//竞赛者的数量
    	if (n < 2)//如果竞赛者的数目小于2,不能进行竞赛
    		throw illegalParameterValue("must have at least 2 players");
    
    	//初始化类内数据成员
    	this->player = thePlayer; //竞赛者
    	this->numberOfPlayers = n;//当前竞赛者的数目
    	delete[] this->tree;      //删除竞赛树
    	this->tree = new int[n];        //创建竞赛树数组
    	
    	//计算s=2^log (n-1)
    	int i, s;
    	for (s = 1; 2 * s <= n - 1; s += s);
    
    	this->lowExt = 2 * (n - s);//最底层外部节点个数(见公式)
    	this->offset = 2 * s - 1;//固定值(见公式)
    
    	//为最低级别的外部节点进行匹配
    	for (i = 2; i <= this->lowExt; i += 2)
    		play((this->offset + i) / 2, i - 1, i);
    
    	//处理剩余的外部节点
    	if (n % 2 == 1) {
    		//特殊情况下奇数n,发挥内部和外部节点
    		play(n / 2, this->tree[n - 1], this->lowExt + 1);
    		i = this->lowExt + 3;
    	}
    	else {
    		i = this->lowExt + 2;
    	}
    
    	//i是最左边剩余的外部节点
    	for (; i <= n; i += 2)
    		play((i - this->lowExt + n - 1) / 2, i - 1, i);
    }
    
    /*
    	对tree[p]节点进行比赛,leftChild为左子节点,rightChild为右子节点
    	如果还有父节点,继续向上比赛
    */
    template<class T>
    void completeWinnerTree<T>::play(int p, int leftChild, int rightChild)
    {
    	//因为为最小赢者树,所以返回值比较小的为赢者
    	this->tree[p] = (this->player[leftChild] <= this->player[rightChild]) ? 
    		leftChild : rightChild;
    
    	//如果是右子节点并且还有父节点,那么就继续向上进行比赛
    	while ((p % 2 == 1) && (p > 1)) {
    		//对父节点进行比赛
    		this->tree[p / 2] = (this->player[tree[p - 1]] <= this->player[tree[p]]) ? 
    			tree[p - 1] : tree[p];
    		p /= 2;//移至父节点
    	}
    }
    
    //在参赛者thePLayer的分数变化后重赛
    template<class T>
    void completeWinnerTree<T>::rePlay(int thePlayer)
    {
    	int n = numberOfPlayers;//竞赛者的数量
    	if (thePlayer <= 0 || thePlayer > n)
    		throw illegalParameterValue("Player index is illegal");
    
    	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;
    
    	// 第二次比赛的特殊情况
    	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 completeWinnerTree<T>::output()const
    {
    	std::cout << "number of players  = " << this->numberOfPlayers
    		<< " lowExt = " << this->lowExt
    		<< " offset = " << this->offset << std::endl;
    
    	//输出每一个节点的赢者
    	std::cout << "complete winner tree pointers are" << std::endl;
    	for (int i = 1; i < this->numberOfPlayers; i++)
    		std::cout << this->tree[i] << ' ';
    	std::cout << std::endl;
    }
    #endif
    • 主函数定义:
    struct player
    {
    	int id, key;
    
    	operator int() const { return key; }
    };
    
    int main()
    {
    	//输入竞赛者的数量
    	int n;
    	std::cout << "Enter number of players, >= 2" << std::endl;
    	std::cin >> n;
    	if (n < 2){
    		std::cout << "Bad input" << std::endl;
    		exit(1);
    	}
    
    	//创建竞赛者数组
    	player *thePlayer = new player[n+1];
    	
    	std::cout << "Create players success" << std::endl;
    
    	//输入每一个竞赛者的键值
    	std::cout << "Enter player values" << std::endl;
    	for (int i = 1; i <= 10; i++)
    	{
    		std::cin >> thePlayer[i].key;
    		thePlayer[i].id = i;
    	}
    	
    	//创建一个赢者树
    	completeWinnerTree<player> *w = new completeWinnerTree<player>(thePlayer, n);
    
    	std::cout << "Create completeWinnerTree success" << std::endl;
    
    	//输出最终的赢者
    	std::cout << "The winner tree is" << std::endl;
    	w->output();
    
    	//改变一个节点的值,然后重新进行比赛
    	thePlayer[2].key = 0;
    	w->rePlay(2);
    	std::cout << "Changed player 2 to zero, new tree is" << std::endl;
    	w->output();
    
    	//改变一个节点的值,然后重新进行比赛
    	thePlayer[3].key = -1;
    	w->rePlay(3);
    	std::cout << "Changed player 3 to -1, new tree is" << std::endl;
    	w->output();
    
    	//改变一个节点的值,然后重新进行比赛
    	thePlayer[7].key = 2;
    	w->rePlay(7);
    	std::cout << "Changed player 7 to 2, new tree is" << std::endl;
    	w->output();
    
    	return 0;
    }

    六、输者树

    • 考察在赢者树中的rePlay操作。在许多应用中,只有在一个新选手替代了前一个赢者之后,才执行这个操作。这是,在从赢者的外部节点到根节点的路径上,所有比赛都要重新进行
    • 考察下图的最小赢者树:
      • 假设赢者f被关键字为5的选手f'取代
      • 重新进行的第一场比赛时在e和f'之间进行,并且f'获胜,e在以前与f的比赛中是输者
      • 赢者f'在内部节点tree[3]的比赛中与g对阵,注意g在tree[3]处于f的前一场比赛中是输者,现在g与tree[3]处f'对阵是赢者
      • 接下来,g在根节点的比赛中与a对阵,而a在根节点处的上一场比赛中是输者

    • 如果每个内部节点记录的是在该节点比赛的输者而不是赢者,那么当赢者player[i]改变后,在从该节点到根的路径上,重新确定每一场比赛的选手所需要的操作量就可以减少。最终的赢者科技路在tree[0]中
    • 下图a与图b相对应的输者树,它有8名选手。当赢者f的关键字编程5时,我们移动带它的父节点tree[6]进行比赛,比赛的选手是player[tree[6]]和player[6]
    • 也就是说,为确定选手f'=player[6]的对手,只需简单地查看tree[6]即可,而在赢者树中,还需要查看tree[6]的其它子节点
    • 在tree[6]的比赛完成后,输者e被记录在此节点,f'继续在tree[3]比赛,对手是前一场的输者g,而g就记录在tree[3]中
    • 这次的输者是fg',它被记录于tree[3]
    • 赢者g则继续在tree[1]比赛,对手是上一场比赛的输者a,而a就记录在tree[1]。这次的输者是g,它被记录在tree[1]。新的输者树如下图b所示

    • 当一个赢者发生变化时,使用输者树可以简化重赛的过程,但是,当其他选手发生变化时,就不是那么回事了。例如,当选手d的关键字由9变成3时,在tree[5]、tree[2]和tree[1]上的比赛将重新进行。在tree[5]的比赛中,d的对手是c,但c不是上一场比赛的输者,因此它没有记录在tree[5]中。在tree[2]的比赛中,d的对手是a,但a也不是上一场比赛的输者。在tree[1]的比赛中,d的对手是f',但f同样不是上一场比赛的输者。为了重新进行这些比赛,还得用到赢者树。因此,仅当player[i]为前次比赛的赢家时,对于函数rePlay(i),采用输者树比采用赢者树执行效率更高
    展开全文
  • 竞赛树 竞赛树的基本操作是替换最大(或最小)元素。如果有n个元素,这个基本操作的用时为O(logn).。虽然用堆和左高树来表示也能用近似的时间

    竞赛树

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

    展开全文
  • 1、竞赛树的相关概念一般将竞赛树分为赢者树和输者树。所谓赢者树,就是对于n名选手,赢者树是一棵含n个外部节点,n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。同理,对于输者树,每个内部...
  • > 线段是一种二叉搜索,与区间相似,它将一个区间划分成一些单元区间,每个单元区间对应线段中的一个叶结点。 > 使用线段可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未...
  • Trie,即字典,又称单词查找或键,是一种结构,是一种哈希的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少...
  • 数据结构、动态规划、基础排序、暴力算法
  • 算法竞赛宝典3-基础数据结构 全国青少年信息学奥林匹克联赛(NOIP)系列复赛教材 本书涉及到基础的数据结构知识,包括链表、堆栈、队列、、图、哈希表、二分图、并查集、线段数等知识。并且对每个知识点及其扩展知识...
  • 数据结构之Trie

    2016-03-28 11:24:01
    Trie,又称字典,单词查找或者前缀,是一种用于快速检索的多叉树结构,如英文字母的字典是一个26叉,数字的字典是一个10叉。 Trie一词来自retrieve,发音为/tri:/ “tree”,也有人读为/traɪ/ ...
  • 数据结构与算法目录为 数据结构与算法(Python) 1. 引入概念 1.1. 第一次尝试 1.2. 算法的提出 1.3. 第二次尝试 1.4. 算法效率衡量 1.5. 算法分析 1.6. 常见时间复杂度 1.7. Python内置类型性能分析 1.8. 数据结构 ...
  • 借助在线评测系统 Aizu Online judge 以及大量例题,详细讲解了算法与复杂度、初等和高等排序、搜索、递归和分治法、动态规划法、二叉搜索、堆、 图、计算几何学、数论等与程序设计竞赛相关的算法和数据结构, 既...
  • 所以在继续拓展线段的应用之前,我们先给大家讲一下线段结构当中的应用(不会线段的同学们可以看看我上次的博客:http://blog.csdn.net/amuseir/article/details/79301619)在算法竞赛当中,结构是...
  • 活用各种数据结构——线段

    千次阅读 2015-09-29 20:17:58
    对《挑战程序设计竞赛》的一个记录第三章 出类拔萃——中级篇3.3活用各种数据结构——线段篇下一篇:3.3活用各种数据结构——RMQ/树状数组/分桶法和平方分割线段树主要还是看胡浩的文章 (完全版线段)- 单点...
  • 树是一种常见的数据结构,得到了非常广泛的应用如文件系统、目录结构、霍夫曼编码等。根据树的特点及应用场景,我们通常会遇到二叉树、平衡树、红黑树、竞赛树、B树等。 在C、C++语言中我们在实现树时需要用到指针...
  • (1)设计实现最小输者树结构 ADTADTADT,ADTADTADT 中应包括初始化、返回赢者、重构等基本操作。 (2)设计实现外排序,外部排序中的生成最初归并串以及 KKK 路归并都用最小输者树结构实现; (3)随机创建一个较长...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,292
精华内容 5,316
关键字:

数据结构竞赛树

数据结构 订阅