数据结构 课件 选择树

《数据结构 课件 选择树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SelectionTreesWinnertrees.LoserTrees.WinnerTreesCompletebinarytreewithnexternalnodesandn-1internalnodes.Externalnodesrepresenttournament(比赛)players.Eachinternalnoderepresentsamatchplayedbetweenitstwochildren;thewinnerofthematch(参赛者)isstoredattheinternalnode.Roothasoverallwi

2、nner.WinnerTreeFor16PlayersplayermatchnodeWinnerTreeFor16Players4368157326945258Smallerelementwins=>minwinnertree.361324253122121WinnerTreeFor16Players4368157326945258heightislog2n(excludesplayerlevel)361324253122121ComplexityOfInitializeO(1)timetoplaymatchateachmatchnode.n

3、-1matchnodes.O(n)timetoinitializenplayerwinnertree.ApplicationsSorting.Insertelementstobesortedintoawinnertree.Repeatedlyextractthewinnerandreplacebyalargevalue.Sort16Numbers4368157326945258361324253122121Sort16Numbers4368157326945258361324253122121Sort16Numbers436815732694

4、5258361324253122121Sortedarray.1Sort16Numbers4368157326945258365324253122121Sortedarray.1Sort16Numbers4368157326945258363532425322121Sortedarray.1Sort16Numbers4368157326945258363532425322321Sortedarray.1Sort16Numbers4368157326945258363532425322322Sortedarray.1Sort16Numbers4

5、36815732694525836353242532232222Sortedarray.12Sort16Numbers436815732694525836353642532232222Sortedarray.12Sort16Numbers436815732694525836353642534232222Sortedarray.12Sort16Numbers436815732694525836353642534232222Sortedarray.12Sort16Numbers436815732694525836353642534232222So

6、rtedarray.12Sort16Numbers4368157326945258363536425342322Sortedarray.122Sort16Numbers4368157326945258363536455342322Sortedarray.122Sort16Numbers4368157326945258363536455345322Sortedarray.122Sort16Numbers4368157326945258363536455345342Sortedarray.122Sort16Numbers4368157326945

7、258363536455345343Sortedarray.122Sort16Numbers4368157326945258363536455345343Sortedarray.1223TimeToSortInitializewinnertree.O(n)timeRemovewinnerandreplay.O(logn)timeRemovewinnerandreplayntimes.O(nlogn)timeTotalsorttimeisO(nlogn).ActuallyTheta(nlogn).ReplaceWinnerAndReplay43

8、68157326945258361324253122121Replacewinnerwith6.ReplaceWinnerAndReplay436865732694