胜者树与败者树

0.前言

查阅了网路上关于胜败者树区别的回答和文章，发现在描述败者树的比较过程中大多一笔带过，容易引起误解，写这一篇笔记更清晰地区分一下两者。

1.简介

胜者树与败者树均是完全二叉树，是树形选择排序的变形。用叶子节点表示待排序元素，中间节点储存两个子节点比较的结果（胜者\败者），根节点即为最终的胜者\败者。

2.比较

比较堆、胜者树、败者树，三者在时间复杂度上没有数量级区别，每一次重构的代价均为$O(log_2n)$。

堆排序

不过三者的复杂度系数上有所区别，当移出已构建好的树的根节点元素后，在加入新元素重构过程中，每调整一层，堆排序需要比较两次：

#i为要下调的元素
if(heap[2*1+1]<heap[2*i+2]) j = 2*1+2; //指向两个child中较大者
if(heap[i]>heap[j]) //较大者再与i比较

而采用胜\败者树的话，就只需要与中间节点存储的胜\败者比较一次。

胜者树与败者树

胜者树每一个中间节点存储的是两个子节点比较得到的胜者，当最终的胜者移出树后，其所在路径上所有中间节点值均变为无效值，加入新值后调整过程中，每调整一层，需要先访问父节点，再访问兄弟节点，从兄弟节点得到兄弟子树的胜者位置，再取该值与新值进行比较，即需要3次访存操作。

败者树的中间节点存储的是两个子节点比较得到的败者（在树的根节点上再添加一个节点存储最终胜者），每次比较的值是用败者位置反选出的胜者，胜者值必然不会被存储到中间节点，所以原胜者移出后中间节点值仍有效，每调整一层，访问父节点，得出父节点中原败者位置（兄弟子树中的胜者 ），与其比较，若败，则更新败者值，胜则保持该节点不变，依次自底向上重复该操作，完成调整，共访存2次。

相比胜者树，败者树不需要访问兄弟节点，在访存上更有优势，因此在实现大量数据的外部排序时，采用败者树具有明显的优势。理解败者树的关键在于，调整过程中，新值所在子树比较时通过败者值反选出胜者参与比较，而兄弟节点的胜者则已经存储在父节点中（前败者值）。