北京郵電大學(xué)計(jì)算機(jī)學(xué)院--離散數(shù)學(xué)-11.2-trees

1、1,2024/3/19,College of Computer Science & Technology, BUPT,§11.2: Applications of Trees,Binary search treesA simple data structure for sorted listsDecision treesMinimum comparisons in sorting algorithmsPrefi

2、x codesHuffman codingGame trees,2,2024/3/19,College of Computer Science & Technology, BUPT,Binary Search Trees,A representation for sorted sets of items.Supports the following operations in Θ(log n) average-case t

3、ime:Searching for an existing item.Inserting a new item, if not already present.Supports printing out all items in Θ(n) time.Note that inserting into a plain sequence ai would instead take Θ(n) worst-case time.,3,202

4、4/3/19,College of Computer Science & Technology, BUPT,,Binary Search Tree Format,Items are stored at individual tree nodes.We arrange for the tree to always obey this invariant:For every item x,Every node in x’s l

5、eft subtree is less than x.Every node in x’s right subtree is greater than x.,7,3,12,1,5,9,15,0,2,8,11,Example:,4,2024/3/19,College of Computer Science & Technology, BUPT,Recursive Binary Tree Insert,procedure inser

6、t(T: binary tree, x: item)v := root[T]if v = null then begin root[T] := x; return “Done” endelse if v = x return “Already present”else if x v}return insert(rightSubtree[T], x),5,2024/3/19,College of Computer Sci

7、ence & Technology, BUPT,Decision Trees,A decision tree represents a decision-making process.Each possible “decision point” or situation is represented by a node.Each possible choice that could be made at that decis

8、ion point is represented by an edge to a child node.In the extended decision trees used in decision analysis, we also include nodes that represent random events and their outcomes.,6,2024/3/19,College of Computer Scienc

9、e & Technology, BUPT,Coin-Weighing Problem,Imagine you have 8 coins, oneof which is a lighter counterfeit, and a free-beam balance.No scale of weight markings is required for this problem!How many weighings are

10、needed to guarantee that the counterfeit coin will be found?,?,7,2024/3/19,College of Computer Science & Technology, BUPT,As a Decision-Tree Problem,In each situation, we pick two disjoint and equal-size subsets of

11、 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,2024/3/19,Colleg

12、e of Computer Science & Technology, BUPT,Applying the Tree Height Theorem,The decision tree must have at least 8 leaf nodes, since there are 8 possible outcomes.In terms of which coin is the counterfeit one.Recall

13、the tree-height theorem, h≥?logm??.Thus the decision tree must have heighth ≥ ?log38? = ?1.893…? = 2.Let’s see if we solve the problem with only 2 weighings…,9,2024/3/19,College of Computer Science & Technology, B

14、UPT,General Solution Strategy,The problem is an example of searching for 1 unique particular item, from among a list of n otherwise identical items. Somewhat analogous to the adage of “searching for a needle in haystac

15、k.”Armed with our balance, we can attack the problem using a divide-and-conquer strategy, like what’s done in binary search.We want to narrow down the set of possible locations where the desired item (coin) could be fo

16、und down from n to just 1, in a logarithmic fashion.Each weighing has 3 possible outcomes.Thus, we should use it to partition the search space into 3 pieces that are as close to equal-sized as possible.This strategy w

17、ill lead to the minimum possible worst-case number of weighings required.,10,2024/3/19,College of Computer Science & Technology, BUPT,General Balance Strategy,On each step, put ?n/3? of the n coins to be searched on

18、each side of the scale.If the scale tips to the left, then:The lightweight fake is in the right set of ?n/3? ≈ n/3 coins.If the scale tips to the right, then:The lightweight fake is in the left set of ?n/3? ≈ n/3 coi

19、ns.If the scale stays balanced, then:The fake is in the remaining set of n ? 2?n/3? ≈ n/3 coins that were not weighed!Except if n mod 3 = 1 then we can do a little better by weighing ?n/3? of the coins on each side.,Y

20、ou can prove that this strategy always leads to a balanced 3-ary tree.,11,2024/3/19,College of Computer Science & Technology, BUPT,Coin Balancing Decision Tree,Here’s what the tree looks like in our case:,123 vs 456,

21、1 vs. 2,,left:123,balanced:78,,right:456,7 vs. 8,,4 vs. 5,,,,L:1,R:2,B:3,,,,L:4,R:5,B:6,,,L:7,R:8,12,2024/3/19,College of Computer Science & Technology, BUPT,Prefix Codes & Huffman Coding,pp. 762-763,13,2024/3

22、/19,College of Computer Science & Technology, BUPT,一. 最優(yōu)樹(shù)問(wèn)題,帶權(quán)二叉樹(shù): 每片樹(shù)葉都帶權(quán)的二叉樹(shù).帶權(quán)二叉樹(shù)的權(quán): 其中 為：帶權(quán) 的樹(shù)葉的通路長(zhǎng)度.,,,14,2024/3/19,College of Computer Science & Technology, BUPT,最優(yōu)樹(shù): 在所有帶權(quán) 的二叉樹(shù)中

23、, 最小的那棵樹(shù).定理 為帶權(quán)的最優(yōu)樹(shù), 則a) 帶權(quán) 的樹(shù)葉 是兄弟.,,,15,2024/3/19,College of Computer Science & Technology, BUPT,b) 以樹(shù)葉 為兒子的分枝點(diǎn),其通路長(zhǎng)最長(zhǎng).定理 為帶權(quán) 的最優(yōu)樹(shù),若將以帶權(quán) 的樹(shù)葉為兒子的分枝點(diǎn)改為

24、帶權(quán) 的樹(shù)葉，得到一新樹(shù) ,也是最優(yōu)樹(shù).,,,,,,16,2024/3/19,College of Computer Science & Technology, BUPT,,解,求解過(guò)程如下,17,2024/3/19,College of Computer Science & Technology, BUPT,,,,,,,,,,,,,,,,,,,18,2024/3/19,College of Com

25、puter Science & Technology, BUPT,有權(quán) 2,3,5,7,11,13,17,19,23,29,31,37,41求相應(yīng)的最優(yōu)樹(shù).,例,19,2024/3/19,College of Computer Science & Technology, BUPT,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,20,2024/3/19,College o

26、f Computer Science & Technology, BUPT,二、二元前綴碼,21,2024/3/19,College of Computer Science & Technology, BUPT,22,2024/3/19,College of Computer Science & Technology, BUPT,√,√,√,×,×,23,2024/3/19,College o

27、f Computer Science & Technology, BUPT,定理,任意一棵二叉樹(shù)都可產(chǎn)生一 個(gè)前綴碼。,定理,任何一個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹(shù)。,24,2024/3/19,College of Computer Science & Technology, BUPT,25,2024/3/19,College of Computer Science & Technology, BUPT,,,,,,,,,

28、,,,,,,,,,,26,2024/3/19,College of Computer Science & Technology, BUPT,例,27,2024/3/19,College of Computer Science & Technology, BUPT,3)設(shè)樹(shù)葉 帶權(quán) 求 處的符號(hào)串表示出現(xiàn)頻率為 的字母,2)求T所對(duì)應(yīng)的前綴碼,28,2024/3/19,Co

29、llege of Computer Science & Technology, BUPT,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,29,2024/3/19,College of Computer Science & Technology, BUPT,30,2024/3/19,College of Computer Science & Technology, BUPT,,,,,,,,,,,,

30、,,,,,,,,,,,,31,2024/3/19,College of Computer Science & Technology, BUPT,,,,,,,,,,,,,,32,2024/3/19,College of Computer Science & Technology, BUPT,Game Trees,Nim,Tic-tac-toe,,33,2024/3/19,College of Computer Scienc