文档章节

赢者树入门

laomd
 laomd
发布于 2017/03/25 10:30
字数 1166
阅读 19
收藏 0

一、定义(definition):有n个选手的一棵赢者树是一棵完全二叉树,它有n个外部节点和n-1个内部节点,每个内部节点记录的是在该节点比赛中获胜的选手。

图片示例:

解释:

    阴影表示的是外部节点,白色是外部节点。可以看到,叶节点必然是外部节点,根节点必然是内部节点。a和b比赛,(按照某种竞赛规则)a获胜,故a、b的根节点为a,以此类推。

 

二、赢者树的表示:

    假设用完全二叉树的数组来表示赢者树。一棵赢者树有n名选手e[1:n],需要n-1个内部节点t[1:n-1],类型为unsigned。各个节点与数组e、t的对应关系如下:

    为了实现这种对应关系,我们必须能够确定外部节点e[i]的父节点t[p]。假设最底层最左边的内部节点编号为s,则s = 2 ^ (log2(n-1))。因此,存在内部节点的最底层一共有n - s(即n - 1 - s + 1)个内部节点,存在外部节点的最底层一共有lowExt = 2 * (n - s)个外部节点,因为每个内部节点必有连个外部节点。例如上图中,n = 5, s = 4,故倒数第二层有1个内部节点,倒数第一层有2个外部节点。倒数第二层最左边的外部节点编号为lowExt + 1 = 3,因为1到lowExt已经被最底层的外部节点编了。

    因此,对于任意一个外部节点e[i],其父节点的编号p可由以下公式给出:

        令offset = 2 * s - 1,则如果i <= lowExt(即最底层),那p = (i + offset) / 2;如果i > lowExt,那p = (i - lowExt + n - 1) / 2。

四、赢者树的修改:

  •     选手d的分数发生改变
    • 它和c的比赛结果可能改变-->若改变,与a的比赛结果也可能改变...
    • 可能影响d-->根节点路径上的节点,遇到比赛结果不再改变时停止
    • O(logn)

五、实现代码:

// player.h
// node type used by winner tree

#ifndef player_
#define player_

struct player
{
   int id, key;

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

#endif
// winerTree.h
// abstract class winner tree
// all methods are pure virtual functions

#ifndef winnerTree_
#define winnerTree_

using namespace std;

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
};
#endif

// complete implement
// winner tree as a complete binary tree mapped into an array
// derives from the ADT winnerTree

#ifndef completeWinnerTree_
#define completeWinnerTree_

#include <iostream>
#include "winnerTree.h"
#include "myExceptions.h"

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);
};

template<class T>
void completeWinnerTree<T>::initialize(T *thePlayer,
                                       int theNumberOfPlayers)
{// Create winner tree for thePlayer[1:numberOfPlayers].
   int n = theNumberOfPlayers;
   if (n < 2)
      throw illegalParameterValue("must have at least 2 players");

   player = thePlayer;
   numberOfPlayers = n;
   delete [] tree;
   tree = new int [n];

   // compute  s = 2^log (n-1)
   int i, 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)
      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;
   }
   else i = lowExt + 2;

   // i is left-most remaining external node
   for (; i <= n; i += 2)
      play((i - lowExt + n - 1) / 2, i - 1, i);
}

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>::rePlay(int thePlayer)
{// Replay matches for player thePlayer.
   int n = numberOfPlayers;
   if (thePlayer <= 0 || thePlayer > n)
      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<class T>
void completeWinnerTree<T>::output() const
{
   cout << "number of players  = " << numberOfPlayers
        << " lowExt = " << lowExt
        << " offset = " << offset << endl;
   cout << "complete winner tree pointers are" << endl;
   for (int i = 1; i < numberOfPlayers; i++)
      cout << tree[i] << ' ';
   cout << endl;
}

#endif

 

© 著作权归作者所有

laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州
私信 提问
牛客网 小白月赛2 F题 黑黑白白 【简单sg博弈】

传送门 题意: 就是每次在一颗有根树上有一个棋子, 两个人轮流的移动棋子, 且每次只能向其儿子移动, 不能移动者输掉比赛, 给定这个树的形态, 问是否先手必胜. 思路: 稍微了解一点sg博弈的都...

anxdada
2018/04/22
0
0
徒步日记三 秦岭崖上树

队友指着悬崖上的树,“这些树真坚韧,峭壁上也能生存”。 一路上看着这些树,最初佩服其坚韧,后觉得聪明,坚韧次之。 峭壁看似危险,实则安全。 首先,提高竞争门槛。那些习惯平原舒适区植...

卧龙小
2016/02/17
44
0
蒙特卡洛树搜索 - 以蛮力对抗智慧

蒙特卡洛树搜索(Monte Carlo tree search;简称:MCTS)是一种用于某些决策过程的启发式搜索算法,最引人注目的是在游戏中的使用。一个主要例子是计算机围棋程序,它也用于其他棋盘游戏、即...

X猪
2018/09/04
0
0
AlphaGo算法原理浅析

2016年3月,AlphaGo与围棋世界冠军、职业九段棋手李世石进行围棋人机大战,以4比1的总比分获胜,震惊世界;2017年5月,AlphaGo与排名世界第一的世界围棋冠军柯洁对战,以3比0的总比分获胜,再...

雪饼
2017/12/25
16
0
Python不能帮你找到女朋友,却能让你成为有钱的单身狗

王者荣耀的团队年终奖是100个月工资、华为的员工房租补贴就有8000块、BAT校招起步价年薪20万……如果你看到这些消息的第一反应就是“炒作”,那只能说,贫穷限制了你的想象力。 一.选对行业,...

bf02jgtrs00xktcx
2017/12/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

U72024 C++初识类

题目 (Circle类)一个圆形的旱冰场地,场地内抹水泥,造价为每平方米20元,围栏用木条围成,每米造价35元。设计一个Circle类,可以求出圆的面积和边长,用户可以此求出旱冰场的造价。请在下...

StupidZhe
43分钟前
8
0
你应该选择哪种树莓派?

本文是《14 天学会树莓派使用》系列文章的第一篇。虽然本系列文章主要面向没有使用过树莓派或 Linux 或没有编程经验的人群,但是肯定有些东西还是需要有经验的读者的,我希望这些读者能够留下...

linux-tao
49分钟前
1
0
动态代理知识详解

动态代理实现的两种方式 给动态代理举个栗子:例如我们平时买笔记本电脑,很多时候都是不从厂家拿货,而是通过经销商买电脑。代理模式出现解决了生产厂家的一些问题,那么这个这个思想在我们...

我叫小糖主
今天
12
0
Calendar TimeZone SimpleDateFormat

关于Calendar类的使用可参考:Java Calendar类的使用总结 获取日历(Calendar):java.util.Calendar#getInstance() 获取时区TimeZone: TimeZone.getTimeZone("GMT+00:00"); 或:TimeZone.ge......

Hzhodor
今天
1
0
这 17 个 JVM 参数,高级 Java 必须掌握

前言 大家都知道,jvm在启动的时候,会执行默认的一些参数。一般情况下,这些设置的默认参数应对一些平常的项目也够用了。但是如果项目特别大了,需要增加一下堆内存的大小、或者是系统老是莫...

编程SHA
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部