数据结构 课件 选择树

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Selection Trees,Winner trees.,Loser Trees.,Winner Trees,Complete binary tree with,n,external nodes and,n-1,internal nodes.,External nodes represent tournament(,比赛,)players.,Each internal node represents a match played between its two children;the winner of the match(,参赛者,)is stored at the internal node.,Root has overall winner.,Winner Tree For 16 Players,player,match node,Winner Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,Smaller element wins,=min winner tree,.,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Winner Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,height is,log,2,n,(excludes player level),3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Complexity Of Initialize,O(1),time to play match at each match node.,n-1,match nodes.,O(n),time to initialize,n,player winner tree.,Applications,Sorting.,Insert elements to be sorted into a winner tree.,Repeatedly extract the winner and replace by a large value.,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Sorted array.,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,5,3,2,4,2,5,3,1,2,2,1,2,1,Sorted array.,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,2,4,2,5,3,2,2,1,2,1,Sorted array.,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,2,4,2,5,3,2,2,3,2,1,Sorted array.,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,2,4,2,5,3,2,2,3,2,2,Sorted array.,1,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,2,4,2,5,3,2,2,3,2,2,2,2,Sorted array.,1,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,2,5,3,2,2,3,2,2,2,2,Sorted array.,1,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,2,5,3,4,2,3,2,2,2,2,Sorted array.,1,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,2,5,3,4,2,3,2,2,2,2,Sorted array.,1,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,2,5,3,4,2,3,2,2,2,2,Sorted array.,1,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,2,5,3,4,2,3,2,2,Sorted array.,1,2,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,5,5,3,4,2,3,2,2,Sorted array.,1,2,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,5,5,3,4,5,3,2,2,Sorted array.,1,2,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,5,5,3,4,5,3,4,2,Sorted array.,1,2,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,5,5,3,4,5,3,4,3,Sorted array.,1,2,2,Sort 16 Numbers,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,3,5,3,6,4,5,5,3,4,5,3,4,3,Sorted array.,1,2,2,3,Time To Sort,Initialize winner tree.,O(n)time,Remove winner and replay.,O(log n)time,Remove winner and replay,n,times.,O(n log n),time,Total sort time is,O(n log n),.,Actually,Theta(n log n),.,Replace Winner And Replay,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Replace winner with,6,.,Replace Winner And Replay,4,3,6,8,6,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Replay matches on path to root.,Replace Winner And Replay,4,3,6,8,6,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Replay matches on path to root.,Replace Winner And Replay,4,3,6,8,6,5,7,3,2,6,9,4,5,2,5,8,3,6,1,3,2,4,2,5,3,1,2,2,1,2,1,Opponent is player who lost last match played at this node.,Loser Tree,Each match node stores the match loser rather than the match winner.,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,3,8,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,1,7,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,1,6,2,9,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,2,8,1,6,4,9,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,5,8,1,6,4,9,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,5,8,1,6,4,9,Min Loser Tree For 16 Players,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,5,8,2,6,4,9,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,5,8,2,6,4,9,1,Winner,Complexity Of Loser Tree Initialize,One match at each match node.,One store of a left child winner.,Total time is,O(n).,More precisely,Theta(n).,Winner,4,3,6,8,1,5,7,3,2,6,9,4,5,2,5,8,4,6,8,3,5,3,7,2,5,5,8,2,6,4,9,1,Replace winner with,9,and replay matches.,9,5,9,3,3,2,Complexity Of Replay,One match at each level that has a match node.,O(log n),More precisely,Theta(log n).,More Selection Tree Applications,k,-way merging of runs during an external merge sort,