算法和数据结构12.ppt

2004-3 L.Chen TOURNAMENT TREES Chapter 10 Tournament Trees Winner trees. Loser Trees. Winner Tree 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 Winner Tree For 16 Players Winner Tree For 16 Players 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. Winner Tree Operations Initialize O(n) time Get winner O(1) time Remove winner and replay O(log n) time More precisely Theta(log n) Tie breaker (player on left wins in case of a tie). Replace Winner And Replay Replace Winner And Replay Replace Winner And Replay Replace Winner And Replay Loser Tree Each match node stores the match loser rather than the match winner. Min Loser Tree For 16 Players Min Loser Tree For 16 Players Min Loser Tree For 16 Players Min Loser Tree For 16 Players Min Loser Tree For 16 Players Min Loser Tree For 16 Players Min Loser Tree For 16 Players 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). Complexity Of Replay One match at each level that has a match node. O(log n) More precisely Theta(log n). Applications Tournament Tree: Run generation. k-way merging of runs during an external merge sort. Truck loading. Truck Loading n packages to be loaded into trucks each package has a weight each truck has a capacity of c tons minimize number of trucks Bin Packing n items to be packed into bins each item has a size each bin has a capacity of c tons minimize number of bins Bin Packing Truck loading is same as bin packing. Truck is a bin that is to be packed (loaded). Package is an item/element. Bin packing to minimize number of bins is NP-hard. Several fast heuristics have been propos