胜利者树与败者树

胜者树与败者树
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。

胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。下面是选择一个最小的数字为最胜利者（见图1所示），第一次把各个数组里面的第一个元素都放进去，这是根据胜利树的规则两两比较，得到最小的值，第一次弄完之后，就得出1数字是胜利的，也就是1是最小的。在下一次输出第二小的数字时候，只需要把1所在的数组里面的元素加进去，然后从叶子节点到根节点一直比较得出第二小的值，这样就减少了很多次无用的比较（见图2所示）。

                        

问题：有20个有序数组，每个数组有500个uint变量，降序排序。要求从这10000个元素中选出最大的500个。有人可能会有疑问，就是如果给定的是奇数个数组，那么这个胜者树是不是不能用了呢，其实是可以的。我们大不了可以加一个数组，把数组的个数凑成偶数。这个新加的数组中的所有元素置为极大值或者极小值。这样，这些元素虽然被构建到胜者树中，但是他们因为是极大或者极小的，所以不被纳入胜者树的计算结果中。所以不会产生影响。这样是比较浪费点空间。如果觉得不想浪费这么多的空间，其实还有个办法，那就是在构建胜者树的时候考虑奇偶。如果x是偶数，那么就分配2*x的空间，把 x-2x-1的元素都赋值。而第0个空间是不用的。第一个空间存储胜者树的根。如果是奇数的情况，算一下要用的节点数。2*(x + 1) - 1个，所以直接分配 2 *（ x + 1） 个节点，把最后一个节点的值置为最大或者最小。下面给出程序代码：

 Fig. 1Fig. 1是一棵败者树。规定数大者败。
b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。
败者树重构过程如下：
将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。Fig. 2       Fig. 2是当b3变为13时，败者树的重构图。        注意，败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。对照Fig. 1来看，b3与结点ls[4]的原值比较，ls[4]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls[4]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。
       败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。 Fig. 3Fig. 3是一棵败者树。规定数大者败。
b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；在根结点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。同理，以此类推，沿着根结点不断比赛，直至结束。 

 

查看更多 下一篇