胜者树和败者树的图解

小咪咪 2022-08-01 06:08 133阅读 0赞

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

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

胜者树与败者树可以在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。.

![胜者树与败者树 - 紫龍劍 - 倚天万里][- _ - 1]

Fig. 2

## 二、败者树 ##

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

![胜者树与败者树 - 紫龍劍 - 倚天万里][- _ - 2]

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\]中。

![2651775755607958867.jpg][]

Fig. 4

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

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

由上可知， 败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。

[- _ -]: http://img.ph.126.net/Na5oPiVpFCH_XJldz7nszQ==/627407723104918988.jpg
[- _ - 1]: http://img.ph.126.net/7VMBZ2qJNOOt-hCC-Oum8w==/1097470934211715382.jpg
[- _ - 2]: http://img.ph.126.net/KuhWQDJJgYv7hmRCKHppAQ==/59109745126108008.jpg
[2651775755607958867.jpg]: http://img.ph.126.net/3eGZA35Xo1MmXzVzsaoXAQ==/2651775755607958867.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 B树，B-树和B+树的区别

B树即二叉搜索树： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小于其关键字的子树，右指针指

我不是女神ヾ/ 2024年02月19日 16:46/ 0 赞/ 86 阅读

相关 B树、B-树、B+树、B*树的定义和区分

参考文章：[B树、B-树、B+树、B\树之间的关系][B_B-_B_B] B树 [B-tree][]树即[B树][B]，B即Balanced，平衡的意思。因

「爱情、让人受尽委屈。」/ 2023年02月18日 14:28/ 0 赞/ 123 阅读

相关数据结构图和树的区别_树和图数据结构之间的区别

![76760f18a6f3ef29d1023946ab85efa9.png][] 数据结构图和树的区别 In this tutorial you will learn a

缺乏、安全感/ 2022年12月07日 13:55/ 0 赞/ 219 阅读

相关 java对大文件的分割、排序、合并(多路归并+败者树)

如何对一个超大文件进行排序,内存不够我们这里使用三步骤:分割(首先将大文件分割成内存够的小文件)、排序（对每个小文件进行排序，我这里是写入的时候就排好序了）、合并（利用

Love The Way You Lie/ 2022年11月17日 11:22/ 0 赞/ 219 阅读

相关胜者树和败者树的图解

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

小咪咪/ 2022年08月01日 06:08/ 0 赞/ 134 阅读

相关败者树（多路归并）

已知顺串 R1\[10,15,16\],R2\[9,20,38\].R3\[20,20,30\], R4\[6,15,25\],R5\[8,15,20\],R6\[9,11,1

落日映苍穹つ/ 2022年03月26日 01:48/ 0 赞/ 253 阅读

相关二叉树的一些性质图解

树的介绍 1. 树的定义树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。 [![aHR0cHM6Ly9pbWFnZXMwLmNuYmxv

野性酷女/ 2021年11月15日 13:36/ 0 赞/ 362 阅读

相关男孩和树[中英文配图]

男孩和树\[中英文配图\] ![85wa\_185215\_if8l\_1.jpg][85wa_185215_if8l_1.jpg] ![74v0\_185231

小灰灰/ 2021年11月11日 23:00/ 0 赞/ 213 阅读

相关 B树、B+树和B*树

一 B树的介绍 B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上

Myth丶恋晨/ 2021年07月24日 22:06/ 0 赞/ 557 阅读

相关重温一下树和图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

青旅半醒/ 2021年06月10日 20:39/ 0 赞/ 260 阅读