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

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

    1 概述

    • 竞赛树分为赢者树和输者树,赢者树更直观,输者树实现更高效。
    • 比赛用二叉树来描述,每个外部节点表示一名选手,每个内部节点表示一场比赛,同一层内部节点代表一轮比赛,可以同时进行。
      在这里插入图片描述
      如果竞赛树是完全二叉树,则对于n个选手的比赛,最少的比赛场次为log2nlog_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={(i+offset)/2ilowExt(ilowExt+n1)/2i&gt;lowExt 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=2log2(n1)s=2^{|log_2(n-1)|}offset=2s1offset=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...

    竞赛树:

    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
    

     

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

    千次阅读 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个元素,这个基本操作的用时为O(logn).。虽然用堆和左高树来表示也能用近似的时间

    竞赛树

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

    展开全文
  • 前面有篇文章提到了二叉树的一些基本操作,此文就来介绍一下一般意义上的... //数据域 int child[MAXN]; //子结点的下标 }node[MAXN]; //结点数组,MAXN为结点上限 此时你可能会想,由于无法预知子结点的个数,因此c
  • 一、竞赛树概述 竞赛树是完全二叉树(或满二叉树) 竞赛树可以用数组来表示,而且存储效率最高 竞赛树的基本操作是替换最大(或最小)元素。如果有n个元素,这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树...
  • 赢者概念: 对于n 名选手,赢者是一棵含n 个外部节点, n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。 图型解析: 为决定一场比赛的赢家,假设每个选手有一得分且赢者取决于对两选手...
  • 挑战程序设计竞赛 算法和数据结构 第8章 ALDS1_7_A:Rooted Tree 原书AC代码: #include using namespace std; #define MAX 100005 #define NIL -1 struct Node{int p,l,r;}; Node T[MAX]; int n,D[MAX]; void ...
  • Trie,即字典,又称单词查找或键,是一种结构,是一种哈希的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少...
  • 1、竞赛树的相关概念一般将竞赛树分为赢者树和输者树。所谓赢者树,就是对于n名选手,赢者树是一棵含n个外部节点,n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。同理,对于输者树,每个内部...
  • > 线段是一种二叉搜索,与区间相似,它将一个区间划分成一些单元区间,每个单元区间对应线段中的一个叶结点。 > 使用线段可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未...
  • 数据结构——线段

    2019-08-19 20:27:05
    数据结构——线段简介实现方式实现 简介 线段是一种能够区间查询、区间修改的二叉树。 实现方式 信息学竞赛中,常使用数组下表模拟指针的方式实现。然而在实际情况中,我们并不知道数据量,因此采用动态分配...
  • //本文代码系《挑战程序设计竞赛2》P153第一版代码+自己理解的注释 题目简述:打印的信息 输入:第一行输入n表示点数,接下n行每行输入节点信息(id k ) 输出:按照格式输出节点信息(格式略) 代码: #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 391
精华内容 156
关键字:

数据结构竞赛树

数据结构 订阅