欢迎来到天天文库
浏览记录
ID:45095945
大小:854.50 KB
页数:43页
时间:2019-11-09
《数据结构 课件 选择树》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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
此文档下载收益归作者所有