-
数据结构与算法——竞赛树
2019-05-28 10:12:211 概述 竞赛树分为赢者树和输者树,赢者树更直观,输者树实现更高效。 比赛用二叉树来描述,每个外部...竞赛树不全是完全二叉树,但是完全二叉树可以是比赛的次数最少,竞赛树也成为选择树。 2 赢者树 2.1 定义 ...1 概述
- 竞赛树分为赢者树和输者树,赢者树更直观,输者树实现更高效。
- 比赛用二叉树来描述,每个外部节点表示一名选手,每个内部节点表示一场比赛,同一层内部节点代表一轮比赛,可以同时进行。
如果竞赛树是完全二叉树,则对于n个选手的比赛,最少的比赛场次为。 - 竞赛树不全是完全二叉树,但是完全二叉树可以是比赛的次数最少,竞赛树也成为选择树。
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]由以下公式给出:
其中,、
(2)初始化
从右孩子开始,逐层往上,且每层从左往右依次考察右孩子选手。
(3)类completeWinnerTreetemplate<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 总结
最先适配法求解箱子问题
相邻适配法求解箱子装载问题 -
C++数据结构与算法 竞赛树, 二叉搜索树
2019-03-22 17:37:42竞赛树: 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)采用输者树比赢者树执行效率高。
-
数据结构与算法C++(十三)竞赛树
2020-08-23 17:36:33 -
【算法竞赛树专题】数据结构——一般意义的树的遍历
2020-10-24 15:20:54前面有篇文章提到了二叉树的一些基本操作,此文就来介绍一下一般意义上的... //数据域 int child[MAXN]; //子结点的下标 }node[MAXN]; //结点数组,MAXN为结点上限 此时你可能会想,由于无法预知子结点的个数,因此c -
C++(数据结构与算法):59---竞赛树/选择树(赢者树、输者树)
2020-01-12 21:25:51一、竞赛树概述 竞赛树是完全二叉树(或满二叉树) 竞赛树可以用数组来表示,而且存储效率最高 竞赛树的基本操作是替换最大(或最小)元素。如果有n个元素,这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树... -
(1小时数据结构)数据结构c++描述(二十一) --- 竞赛树及其装箱应用
2020-07-22 18:11:49赢者树概念: 对于n 名选手,赢者树是一棵含n 个外部节点, n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。 图型解析: 为决定一场比赛的赢家,假设每个选手有一得分且赢者取决于对两选手... -
挑战程序设计竞赛 算法和数据结构 第8章 树
2017-09-20 14:19:07挑战程序设计竞赛 算法和数据结构 第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 ... -
『ACM--数据结构--字典树』信息竞赛进阶指南--Tire树
2020-04-23 08:24:33Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少... -
数据结构与算法C++描述(13)---竞赛树及其在箱子装载问题中的应用
2017-11-01 20:48:191、竞赛树的相关概念一般将竞赛树分为赢者树和输者树。所谓赢者树,就是对于n名选手,赢者树是一棵含n个外部节点,n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。同理,对于输者树,每个内部... -
『ACM-数据结构』信息竞赛进阶指南--线段树
2020-04-23 08:35:06> 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 > 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未... -
数据结构——线段树
2019-08-19 20:27:05数据结构——线段树简介实现方式实现 简介 线段树是一种能够区间查询、区间修改的二叉树。 实现方式 信息学竞赛中,常使用数组下表模拟指针的方式实现。然而在实际情况中,我们并不知道数据量,因此采用动态分配... -
【数据结构】树的表达
2020-09-12 10:46:18//本文代码系《挑战程序设计竞赛2》P153第一版代码+自己理解的注释 题目简述:打印树的信息 输入:第一行输入n表示点数,接下n行每行输入节点信息(id k ) 输出:按照格式输出节点信息(格式略) 代码: #...
-
2021年 系统架构设计师 系列课
-
MySQL Router 实现高可用、负载均衡、读写分离
-
MySQL 高可用工具 DRBD 实战部署详解
-
image-api.zip
-
PAT 甲级 1035 Password
-
mac快捷键大全(持续更新中)
-
【ssm项目源码】医院住院管理系统.zip
-
鸿蒙系统Harmonyos源码架构分析-第1期第2课
-
牛牛量化策略交易
-
《书择十本》读后感
-
基于电商业务的全链路数据中台落地方案(全渠道、全环节、全流程)
-
基于Qt的LibVLC开发教程
-
vc定制文件打开对话框,实现文本预览.visual c++
-
基于python的dango框架购物商城毕业设计毕设源代码使用教程
-
如何使用css画出一个倒立的三角形?
-
十六题
-
vc通过钩子,拦截复制操作.zip
-
FTP 文件传输服务
-
2021年R1快开门式压力容器操作答案解析及R1快开门式压力容器操作证考试
-
《血疫:埃博拉的故事》读书摘记