PRELOADER

Dinghow的个人博客

Current post : 《胜者树与败者树》

12/4/2018 —— 

胜者树与败者树

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次访存操作。

img1

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

img2

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