[选择树] 胜者树 | 败者树

本文主要是介绍[选择树] 胜者树 | 败者树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文链接：https://www.yuque.com/cppdev/algo/rwvwes

胜者树/败者树

【胜者树/败者树】

1. 都是完全二叉树，是树形选择排序的一种变形。每个叶子结点相当于一个选手，每个中间结点相当于一个比赛，每一层相当于一轮比赛
2. 不同：胜者树中间结点记录的是胜者的标号；而败者树的中间结点是记录败者的标号

【评价】

1. 胜者树/败者树可以在log(n)的时间内找到最值
2. 任何一个叶子结点的值改变后，利用中间结点的信息，还能够快速地找到最值

败者树

【数据结构】两个数组

1. b[]：下标i为选手的号码，b[i]为选手的能力
2. ls[]：存放败者的记录，ls[0]为正常的胜利者

【建树】两个子节点比较(b3、b4)，败者(b4)放入它们的父结点(ls[4])，而胜者(b3)送到它们的父结点的父结点再和别人PK。如此重复，即可以把最后的胜者推到败者树根结点的父结点中（如图ls[0]）

【调整】胜者（b[3]）从树中被摘除，然后有新的元素替换胜者的位置（b[3]）

1. 新的元素（b[3]）和它的父结点（ls[4]）继续比较，PK后败者放入父结点中，胜者被送上去继续PK

【优点】在继续比较时，它不用和所有叶子的关键字比较，只需沿着相应的叶子结点到根结点的路径调整败者树，这样可以减少比较次数

【代码】

#define LEN 5//败者树容量，多路归并数目
#define MIN -1//所有数据的可能最小值int ls[LEN+1];//败者树,ls[0]存放胜者，其余存放败者
int buf[LEN+1];//存放多路归并的头元素值,多出来的一位放MIN//当改变一个选手的值，需要调整以维持败者树的形态。败者树只需调整选手的父节点即可
//1. 当子节点的值大于父节点，则子节点记录于父节点（小为胜利，记录败者），父节点继续与其父节点比赛
//2. 若子节点小于父节点，则直接使用子节点进行下一轮比赛。
void adjust(int s,int *buf){//s是需要调整的buf的下标int t=(s+LEN)/2;//得到s的在败者树上面的父节点while(t>0){//不断与父节点对比，直到败者树的根节点if(buf[s]>buf[ls[t]]){//如果当前节点s（胜者）大于父节点ls[t]^=s;//交换ls[t]和ss^=ls[t];//s记录胜者ls[t]^=s;//父节点记录败者}t/=2;//得到败者树的上一个父节点，继续与当前胜者s比较}ls[0]=s;//最终的胜者记录于ls[0]
}// 在参赛者数组b[]的最后添加一位，存放一个参赛选手的绝对最小值（选手都是正数的话，如-1）
// 所有中间节点都记录这个最小值的下标。然后依次调整（adjust()）各个选手即可
void build(int *buf){buf[LEN]=MIN;//最后一位放MINfor(int i=0;i<LEN+1;++i)ls[i]=LEN;//所有败者树初始化为MIN的下标for(i=0;i<LEN;++i)adjust(i,buf);//依次调整即可完成初始化
}int main()
{//初始bufint tmp[5]={18,21,16,11,19};memcpy(buf,tmp,LEN*sizeof(int));build(buf);cout<<buf[ls[0]]<<endl;//输出11//取出11后，buf[3]=17int tmp1[5]={18,21,16,17,19};memcpy(buf,tmp1,LEN*sizeof(int));adjust(3,buf);cout<<buf[ls[0]]<<endl;//输出16return 0;
}

【应用】

1. 败者树：外部排序中的应用

这篇关于[选择树] 胜者树 | 败者树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---