（转）败者树 和 胜者树---数组实现

转自：http://blog.csdn.net/sqx2011/article/details/8241734

胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。

      不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。

       胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。

一、胜者树

       胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。

Fig. 1

Fig.1是一个胜者树的示例。规定数值小者胜。

  1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
  2. b3 PK b0，b3胜b0负，内部结点ls[2]的值为3；
  3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
  4. b3 PK b1，b3胜b1负，内部结点ls[1]的值为3。.

当Fig. 1中叶子结点b3的值变为11时，重构的胜者树如Fig. 2所示。

  1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
  2. b3 PK b0，b0胜b3负，内部结点ls[2]的值为0；
  3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
  4. b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。.

Fig. 2

用胜者树对n个节点实现排序操作，构建胜者树和构建堆比较相似，区别在于胜者树只有叶子节点存放了数据，中间节点记录的是叶子节点间的关系。

leaves[n+1]:共有n个叶子节点，存储下标从1到n

successTree[n]:存储中间节点，存储下标从1到n-1

对successTree中的数据从n-1到1，按照优胜策略不断调整内部节点的数值，最后得到一颗胜者树

冠军节点的下标存储在successTree[1]里，实现排序操作时，将该叶子节点的值打印输出，并用一个比叶子节点中所有值都大的值MAX替换，然后对树进行调整。胜者树的调整是从叶子节点到根节点的自下而上的调整，每次都比较双亲节点的左右孩子节点，并把优胜者的下标志存储在双亲节点中。

[cpp] view plaincopy
 
  1. #include <stdio.h>  
  2.  #define K 10  
  3.  #define MAX 65535  
  4.  int leaves[K+1];  
  5.  int successTree[K];  
  6.    
  7.  /* 对于单个内部节点进行调整 */  
  8.  void adjust(int i)  
  9.  {  
  10.      int m,n;  
  11.      if(2 * i < K)               /* 获取它的左孩子结点 */  
  12.          m = successTree[2 * i];  
  13.      else  
  14.          m = 2 * i - K + 1;  
  15.      if(2*i+1<K)                 /* 获取它的右孩子节点 */  
  16.          n = successTree[2*i+1];  
  17.      else  
  18.          n = 2 * i + - K + 2;  
  19.      successTree[i] = leaves[m] > leaves[n] ? n : m; /* 进行胜负判定 */  
  20.  }  
  21.  /* 初始化叶子节点并对内部节点进行类似于堆的调整 */  
  22.  void initTree()  
  23.  {  
  24.      for(int i=1;i<K+1;i++)  
  25.          scanf("%d", &leaves[i]);  
  26.      for(int i=K-1;i>0;i--)  
  27.          adjust(i);  
  28.  }  
  29.  /* 自下而上对胜者树进行调整 */  
  30.  void adjustToRoot(int i)  
  31.  {  
  32.      int parent = (i + K - 1) / 2; /* 对从当前节点到根节点路径上的所有 
  33.                                     * 节点进行调整 */  
  34.      while(parent>0)  
  35.      {  
  36.          adjust(parent);  
  37.          parent = parent / 2;  
  38.      }  
  39.  }  
  40.    
  41.  int main()  
  42.  {  
  43.      freopen("in","r",stdin);  
  44.      initTree();  
  45.      for(int i=1;i<K+1;i++)      /* 每次用最大值替换掉冠军节点，并对树 
  46.                                   * 进行调整,最终得到升序排序的序列 */  
  47.      {  
  48.          printf("%d ", leaves[successTree[1]]);  
  49.          leaves[successTree[1]]=MAX;  
  50.          adjustToRoot(successTree[1]);  
  51.      }  
  52.      return 0;  
  53.  }  

 

二、败者树

       败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

Fig. 3

Fig. 3是一棵败者树。规定数大者败。

  1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；
  2. b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；
  3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；
  4. b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；
  5. 在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。

败者树重构过程如下：

  • 将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。
  • 比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。

Fig. 4

       Fig. 4是当b3变为13时，败者树的重构图。

       注意，败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较，而胜者树则需要和兄弟节点比较。对照Fig. 3来看，b3与结点ls[4]的原值比较，ls[4]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls[4]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。

        败者树常常用于多路外部排序，对于K个已经排好序的文件，将其归并为一个有序文件。败者树的叶子节点是数据节点，两两分组，内部节点记录左右子树中的“败者”，优胜者往上传递一直到根节点，如果规定优胜者是两个数中的较小者，则根节点记录的是最后一次比较中的败者，也就是第二小的数，而用一个变量来记录最小的数。把最小值输出以后，用一个新的值替换最小值节点的值（在文件归并的时候，如果文件已经读完，可以用一个无穷大的数来替换），接下来维护败者树，从更新的节点往上，一次与父节点比较，将败者更新，胜者继续比较。

        注意：当叶子节点的个数变动的时候需要完全重新构建整棵树。

       比较败者树和堆的性能

       败者树在维护的时候，比较次数是logn+1,  败者树从下往上维护，每上一层，只需要和父节点比较一次，而堆是自上往下维护，每一层需要和左右子节点都比较，需要比较两次，从这个角度，败者树比堆更优一点，但是，败者树每一次维护，必然是从叶子节点到根节点的一条路径，而堆维护的时候有可能在中间某个层次停止，这样败者树虽然每层比堆比较的次数少，但是堆比较的层数可能比较少。

        

       从n个数中找出最大的k个，分别用堆和败者树来实现

       堆实现： 维护一个大小为k的小顶堆，每来一个数都和堆顶进行比较，如果比堆顶小，直接舍弃，否则替换堆顶，维护堆，直到n个数都处理完毕，时间复杂度为O(nlogk)

       败者树实现：当用数组来实现败者树时， 维护一个叶子节点个数为k的败者树，注意是叶子节点个数而不是所有节点个数，数字较小者取胜，则最顶层保存的是值最小的叶子节点，每来一个数和最小值比较，如果比最小值还小，直接舍弃，否则替换最小值的节点值，从下往上维护败者树，最后的k个叶子节点中保存的就是所有数中值最大的k的，时间复杂度为O(nlogk)

     

       用数组实现败者树的时候，因为只有叶子节点存储的是数据，因此败者树使用的内存空间是堆的两倍。

       完全树的内部，度数为2的节点个数是叶子节点个数减一 ，所以使用的数组大小为2k-1, 如果把最值也存入数组中，则需要的数组大小为2k

       败者树的构造

       思路： 先构造一颗空的败者树，然后把叶子节点一个一个的插入败者树，自底向上不断的调整，保持内部节点保存的都是失败者的节点编号，优胜者一直向上不断比较，最终得到一颗合格的败者树。

leaves[K+1] : 叶子节点的个数为K，下标从1到K，下标0处存储一个最小值，用来初始化败者树

loserTree[K]: 冠军节点存储在下标0，下标1到K-1存储内部节点

[cpp] view plaincopy
 
  1. int loserTree[K];               /* 存储中间节点值，下标0处存储冠军节点 */  
  2. int leaves[K+1];                /* 从下标1开始存储叶子节点值，下标0处存储一个最小值节点 */  
  3.   
  4. void adjust(int i)  
  5. {  
  6.     int parent=(i+K-1)/2;      /* 求出父节点的下标 */  
  7.     while(parent>0)  
  8.     {  
  9.         if(leaves[i]>leaves[loserTree[parent]])  
  10.         {  
  11.             int temp=loserTree[parent];  
  12.             loserTree[parent]=i;  
  13.             /* i指向的是优胜者 */  
  14.             i= temp;  
  15.         }  
  16.         parent = parent / 2;  
  17.     }  
  18.     loserTree[0]=i;  
  19. }  
  20.   
  21. void initLoserTree()  
  22. {  
  23.     int i;  
  24.     for(i=1;i<K+1;i++)  
  25.         scanf("%d",&leaves[i]);  
  26.     leaves[0]=MIN;  
  27.     for(int i=0;i<K;i++)  
  28.         loserTree[i]=0;  
  29.     for(int i=K;i>0;i--)  
  30.         adjust(i);  
  31. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/sunshisonghit/p/4455691.html