1、1* College of Computer Science return “Done” endelse if v = x return “Already present”else if x vreturn insert(rightSubtreeT, x)5* College of Computer Science & Technology, BUPTDecision Trees n A decision tree represents a decision-making process.n Each possible “decision point” or situation is repr
2、esented by a node.n Each possible choice that could be made at that decision point is represented by an edge to a child node.n In the extended decision trees used in decision analysis, we also include nodes that represent random events and their outcomes.6* College of Computer Science & Technology,
3、BUPTCoin-Weighing Problemn Imagine you have 8 coins, oneof which is a lighter counterfeit, and a free-beam balance.n No scale of weight markings is required for this problem!n How many weighings are needed to guarantee that the counterfeit coin will be found?7* College of Computer Science & Technolo
4、gy, BUPTAs a Decision-Tree Problemn In each situation, we pick two disjoint and equal-size subsets of coins to put on the scale.The balance then“decides” whether to tip left, tip right, or stay balanced.A given sequence ofweighings thus yieldsa decision tree withbranching factor 3.8* College of Comp
5、uter Science & Technology, BUPTApplying the Tree Height Theoremn The decision tree must have at least 8 leaf nodes, since there are 8 possible outcomes.n In terms of which coin is the counterfeit one.n Recall the tree-height theorem, hlogm.n Thus the decision tree must have heighth log38 = 1.893 = 2
6、.n Lets see if we solve the problem with only 2 weighings9* College of Computer Science & Technology, BUPTGeneral Solution Strategyn The problem is an example of searching for 1 unique particular item, from among a list of n otherwise identical items. n Somewhat analogous to the adage of “searching
7、for a needle in haystack.”n Armed with our balance, we can attack the problem using a divide-and-conquer strategy, like whats done in binary search.n We want to narrow down the set of possible locations where the desired item (coin) could be found down from n to just 1, in a logarithmic fashion.n Ea
8、ch weighing has 3 possible outcomes.n Thus, we should use it to partition the search space into 3 pieces that are as close to equal-sized as possible.n This strategy will lead to the minimum possible worst-case number of weighings required.10* College of Computer Science & Technology, BUPTGeneral Ba
9、lance Strategyn On each step, put n/3 of the n coins to be searched on each side of the scale.n If the scale tips to the left, then:n The lightweight fake is in the right set of n/3 n/3 coins.n If the scale tips to the right, then:n The lightweight fake is in the left set of n/3 n/3 coins.n If the scale stays balanced, then:n The fake is in the remaining set of n 2n/3 n/3 coins that were not weighed!n Except if n mod 3 = 1 then we can do a little better by weighing n/3 of the coins on each side.You can prove that this strategy always leads to a balanced 3-ary tree.
