北京郵電大學計算機學院--離散數(shù)學-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)樹問題,帶權二叉樹: 每片樹葉都帶權的二叉樹.帶權二叉樹的權: 其中 為：帶權 的樹葉的通路長度.,,,14,2024/3/19,College of Computer Science & Technology, BUPT,最優(yōu)樹: 在所有帶權 的二叉樹中

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

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

25、puter Science & Technology, BUPT,有權 2,3,5,7,11,13,17,19,23,29,31,37,41求相應的最優(yōu)樹.,例,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,定理,任意一棵二叉樹都可產(chǎn)生一 個前綴碼。,定理,任何一個前綴碼都對應一棵二叉樹。,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)設樹葉 帶權 求 處的符號串表示出現(xiàn)頻率為 的字母,2)求T所對應的前綴碼,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